【luogu P1113 杂务】 题解

题目链接：https://www.luogu.org/problemnew/show/P1113

菜

#include <queue>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

const int maxn = 50000 + 10;

const int inf = 0x7fffffff;

int n, m, s, dis[maxn], w[maxn], du[maxn], ans;

bool vis[maxn];

queue<int> q;

struct edge{

	int from, to, next, len;

}e[maxn<<2];

int head[maxn], cnt;

void add(int u, int v, int w)

{

	e[++cnt].from = u;

	e[cnt].len = w;

	e[cnt].next = head[u];

	e[cnt].to = v;

	head[u] = cnt;

}

void SPFA(int s)

{

	while(!q.empty()) q.pop();

	for(int i = 1; i <= n; i++) dis[i] = inf, vis[i] = 0;

	q.push(s);

	dis[s] = w[s];

	vis[s] = 1;

	while(!q.empty())

	{

		int now = q.front(); q.pop();

		vis[now] = 0;

		for(int i = head[now]; i != -1; i = e[i].next)

		{

			if(dis[e[i].to] > dis[now] + e[i].len)

			{

				dis[e[i].to] = dis[now] + e[i].len;

				if(!vis[e[i].to])

				{

					q.push(e[i].to);

					vis[e[i].to] = 1;

				}

			}

		}

	}

}

int main()

{

	memset(head, -1, sizeof(head));

	scanf("%d",&n);

	for(int i = 1; i <= n; i++)

	{

		int uu, vv, ww;

		scanf("%d%d",&vv,&ww);

		w[vv] = -1*ww;

		while(scanf("%d",&uu) && uu != 0)

		{

			add(uu, vv, -1*ww);

			du[vv]++;

		}

	}

	//for(int i = 1; i <= n; i++) cout<<w[i]<<" ";

	for(int i = 1; i <= n; i++)

	{

		ans = inf;

		if(du[i] == 0) SPFA(i);

		for(int j = 1; j <= n; j++)

		{

			if(ans > dis[j])

			ans = dis[j];

		}

	}

	printf("%d",-ans);

	return 0;

}