比赛 4043级NOIP2022欢乐赛2nd 评测结果 AAAAAAAAAA
题目名称 奶牛排队 最终得分 100
用户昵称 ZRQ 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2022-10-31 21:29:01
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define ll long long
using namespace std;
const int N=1005,M=100005;
int n,x,y;
int hd[N],nt[M],e[M],idx,cnt[N];
ll dis[N],w[M],INF;
bool vis[N];
inline void add(int x,int y,ll k)
{
	nt[++idx]=hd[x],hd[x]=idx,e[idx]=y,w[idx]=k;
}
void SPFA()
{
	memset(dis,0x3f,sizeof(dis));
	INF=dis[0];
	queue<int> q;
	q.push(1);
	dis[1]=0;
	while(!q.empty())
	{
		int cur=q.front();
		q.pop();
		vis[cur]=0;
		for(int i=hd[cur];i;i=nt[i])
			if(dis[e[i]]>dis[cur]+w[i])
			{
				dis[e[i]]=dis[cur]+w[i];
				if(!vis[e[i]])
				{
					++cnt[e[i]];
					if(cnt[e[i]]==n+1)
					{
						puts("-1");
						exit(0);
					}
					q.push(e[i]),vis[e[i]]=1;
				}
			 } 
	}
	if(dis[n]==INF) puts("-2");
	else printf("%lld\n",dis[n]);
	return ;
}
int main()
{
	freopen("layout.in","r",stdin);
	freopen("layout.out","w",stdout);
	scanf("%d%d%d",&n,&x,&y);
	ll d;
	for(int i=1,a,b;i<=x;++i) scanf("%d%d%lld",&a,&b,&d),add(a,b,d);
	for(int i=1,a,b;i<=y;++i) scanf("%d%d%lld",&a,&b,&d),add(b,a,-d);
	SPFA();
	return 0;
}