比赛 |
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;
}