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