65分WA求助
查看原帖
65分WA求助
342868
qfpjm楼主2021/8/18 19:13
#include <bits/stdc++.h>

using namespace std;

struct edge
{
	int u, v, w;
	edge() {}
	edge(int a, int b, int c) : u(a), v(b), w(c) {}
};

vector<edge> e[100005];
int n, m, dis[100005], cnt[100005];
bool inque[100005];

bool SPFA(int start)
{
	queue<int> que;
	que.push(start);
	cnt[start] ++;
	dis[start] = 0;
	inque[start] = true;
	while (!que.empty())
	{
		int u = que.front();
		que.pop();
		inque[u] = false;
		for (int i = 0 ; i < e[u].size() ; i ++)
		{
			int v = e[u][i].v;
			int w = e[u][i].w;
			if (dis[u] + w < dis[v])
			{
				dis[v] = dis[u] + w;
				if (!inque[v])
				{
					inque[v] = true;
					que.push(v);
					cnt[v] ++;
					if (cnt[v] == n)
					{
						return false;
					}
				}
			}
		}
	}
	return true;
}

int main()
{
	cin >> n >> m;
	for (int i = 1 ; i <= m ; i ++)
	{
		int op;
		cin >> op;
		if (op == 1)
		{
			int x, y, z;
			cin >> x >> y >> z;
			e[x].push_back(edge(x, y, -z));
		}
		else if (op == 2)
		{
			int x, y, z;
			cin >> x >> y >> z;
			e[y].push_back(edge(y, x, z));
		}
		else
		{
			int x, y;
			cin >> x >> y;
			e[x].push_back(edge(x, y, 0));
			e[y].push_back(edge(y, x, 0));
			break;
		}
	}
	for (int i = 1 ; i <= n ; i ++)
	{
		e[n + 1].push_back(edge(n + 1, i, 0));
	}
	memset(dis, 0x3f, sizeof(dis));
	if (SPFA(n + 1))
	{
		cout << "Yes";
	}
	else
	{
		cout << "No";
	}
	return 0;
}
2021/8/18 19:13
加载中...