比赛 4043级NOIP2022欢乐赛2nd 评测结果 AWAAAWAWAA
题目名称 奶牛排队 最终得分 70
用户昵称 yrtiop 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2022-10-31 20:27:23
显示代码纯文本
#include <bits/stdc++.h>
#define pb push_back
using pii = std::pair<int,int>;

const int maxn = 1e3 + 5;
int n,x,y,pre[maxn],dis[maxn],res[maxn];
std::vector<pii> G[maxn];
bool vis[maxn];

int find(int x) {
	return x == pre[x] ? x : pre[x] = find(pre[x]);
}

bool SPFA() {
	memset(vis , false , sizeof(vis));
	memset(dis , 0x3f , sizeof(dis));
	dis[0] = 0;
	std::queue<int> q;
	q.emplace(0);
	vis[0] = true;
	while(!q.empty()) {
		int u = q.front();
		q.pop();
		if(++ res[u] >= n)return false;
		for(auto& p : G[u]) {
			int v,w;
			std::tie(v , w) = p;
			if(dis[v] > dis[u] + w) {
				dis[v] = dis[u] + w;
				if(!vis[v])
					q.emplace(v),vis[v] = true;
			}
		}
	}
	return true;
}

int main() {
	freopen("layout.in","r",stdin);
	freopen("layout.out","w",stdout);
	scanf("%d %d %d",&n,&x,&y);
	for(int i = 1;i <= n;++ i)
		pre[i] = 1;
	for(int i = 1;i <= x;++ i) {
		int a,b,d;
		scanf("%d %d %d",&a,&b,&d);
		if(find(a) != find(b))pre[find(b)] = find(a);
		G[a].pb({b , d});
	}
	for(int i = 1;i <= y;++ i) {
		int a,b,d;
		scanf("%d %d %d",&a,&b,&d);
		if(find(a) != find(b))pre[find(b)] = find(a);
		G[b].pb({a , -d});
	}


	if(find(1) != find(n)) {
		puts("-2");
		return 0;
	}

	for(int i = 1;i <= n;++ i)G[0].pb({1 , 0});
	if(!SPFA())puts("-1");
	else printf("%d\n",dis[n] - dis[1]);
	return 0;
}