求调qwq
查看原帖
求调qwq
361592
histcat楼主2022/7/17 09:06
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<queue>
#include<cstring>
using namespace std;
const int N = 5e3 + 10;

int h[N],ne[N],to[N],val[N],idx = 1;

long long dis[N]; int st[N], num[N];

int n ,m;
int t, a, b, c;

void add(int x, int y, int z)
{
	val[++idx] = z;
	to[idx] = y;
	ne[idx] = h[x];
	h[x] = idx;
}

bool spfa(int x)
{
	memset(dis, 0x3f, sizeof dis);
	queue<int> qwq;
	qwq.push(x);
	dis[x] = 0;
	st[x] = 1;
	num[x] = 1;
	while(qwq.size())
	{
		int u = qwq.front();
		qwq.pop();
		st[u] = 0;
		
		for(int v = h[u]; v != 0; v = ne[v])
		{
			int j = to[v];
			if(dis[j] > dis[u] + val[v])
			{
				dis[j] = dis[u] + val[v];
				if(!st[j])
				{
					if(!st[j])
					{
						qwq.push(j);
						st[j] = true;
					}
					num[j] ++;
					if(num[j] > n)
					{
						cout << j << endl;
						return false;
					}
				}
			}
		}	
	}
	return true;
}

int main()
{
	freopen("in.in","r", stdin);
	freopen("out.out", "w", stdout);
	scanf("%d%d", &n, &m);
	for(int i = 1;i <= n;i++)
	{
		scanf("%d", &t);
		if(t == 1)
		{
			scanf("%d%d%d", &a, &b ,&c);
			add(a, b, -c);
		}
		else if(t == 2)
		{
			scanf("%d%d%d", &a, &b ,&c);
			add(b, a, c);
		}
		else
		{
			scanf("%d%d", &a, &b);
			add(b, a, 0);
			add(a, b, 0);
		}
	}
	for(int i = 1;i <= n;i++)
	{
		add(n + 1, i, 0);
	}
	
	
	if(!spfa(n + 1))
	{
		printf("No");
	}
	else
	{
		printf("Yes");
	}

	
	return 0;
}
2022/7/17 09:06
加载中...