比赛 4043级NOIP2022欢乐赛2nd 评测结果 AAAAAAAAAA
题目名称 奶牛排队 最终得分 100
用户昵称 op_组撒头屯 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2022-10-31 20:01:31
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1000+10;
const int M=5000*3+5;
struct sf{
	int to,next;ll w;
}eg[M];
int head[N],ne=0;
int n,x,y,m;
void add(int x,int y,ll w){
	eg[++ne]={y,head[x],w};
	head[x]=ne;return ;
}
bool ins[N];
int cnt[N]={0};
ll d[N];
queue<int>q;
void spfa(){
	memset(d,0x3f,sizeof(d));
	ins[1]=1;cnt[1]++;
	q.push(1);d[1]=0;
	while(!q.empty()){
		int t=q.front();q.pop();
		ins[t]=0;
		for (int i=head[t];i!=0;i=eg[i].next){
			int v=eg[i].to;ll w=eg[i].w;
			if (d[t]+w<d[v]){
				d[v]=d[t]+w;
				if (!ins[v]){
					q.push(v);ins[v]=1;
					cnt[v]++;
					if (cnt[v]>n){
						printf("-1\n");return ;
					}
				}
			}
		}
	}
	if (d[n]==d[0]){
		printf("-2\n");return ;
	}
	printf("%lld\n",d[n]);return ;
}
int main(){
	freopen ("layout.in","r",stdin);
	freopen ("layout.out","w",stdout);
	scanf("%d%d%d",&n,&x,&y);m=x+y;
	for (int i=1;i<n;i++)add(i+1,i,0);
	for (int i=1;i<=x;i++){
		int x,y,d;scanf("%d%d%d",&x,&y,&d);
		add(x,y,d);
	}
	for (int i=1;i<=y;i++){
		int x,y,d;scanf("%d%d%d",&x,&y,&d);
		add(y,x,-d);
	}
	spfa();
}