差分约束的裸题。。
下午心态爆的厉害，No都没输出直接打了return 0；。。。。
#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; struct node { int x,y,d,next; }a[21000];int len,last[11000]; void ins(int x,int y,int d) { len++; a[len].x=x;a[len].y=y;a[len].d=d; a[len].next=last[x];last[x]=len; } int sta[11000];bool v[11000]; int d[11000],vis[11000]; int main() { int n,m,x,y,c,op; scanf("%d%d",&n,&m); len=0;memset(last,0,sizeof(last)); for(int i=1;i<=m;i++) { scanf("%d",&op); if(op==3) { scanf("%d%d",&x,&y); ins(x,y,0); ins(y,x,0); } else if(op==1) { scanf("%d%d%d",&x,&y,&c); ins(x,y,-c); } else if(op==2) { scanf("%d%d%d",&x,&y,&c); ins(y,x,c); } } int top=0; for(int i=1;i<=n;i++)sta[++top]=i; memset(d,63,sizeof(d));d[sta[top]]=0; memset(v,true,sizeof(v)); memset(vis,0,sizeof(vis)); while(top!=0) { int x=sta[top];top--; for(int k=last[x];k;k=a[k].next) { int y=a[k].y; if(d[y]>d[x]+a[k].d) { d[y]=d[x]+a[k].d; vis[y]=vis[x]+1; if(vis[y]>n){printf("No ");return 0;} if(v[y]==false) { v[y]=true; sta[++top]=y; } } } v[x]=false; } printf("Yes "); return 0; }