比较简单:
#include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <iostream> #include <queue> #include <stack> using namespace std; const int M = 9999; const int N = 109; const int INF = 0x3f3f3f3f; struct LT{ int to,nex,val; }L[M]; int F[N],cnt; void add(int f,int t,int d) { L[cnt].to = t; L[cnt].nex = F[f]; L[cnt].val = d; F[f] = cnt++; } int n,m,p,dis[N],inque[N],con[N]; int que[N*N]; void solve() { memset(dis,0,sizeof(dis)); memset(con,0,sizeof(con)); for(int i=0;i<n;i++) que[i]=i,inque[i] = 1; int fin = 0; int front=0,rear =n; while(rear>front) { int e =que[front++]; con[e]++; if(con[e]>=n) { fin = true; break; } inque[e] = 0; for(int i=F[e];i;i=L[i].nex) { int to =L[i].to; if(dis[to]>dis[e]+L[i].val) { dis[to] = dis[e]+L[i].val; if(!inque[to]) { inque[to] = true; if(con[to]>(n>>1)&&front>0) que[--front]=to; else que[rear++] = to; } } } } if(fin) printf("YES\n"); else printf("NO\n"); } int main() { freopen("in.txt","r",stdin); int cas,T=1; scanf("%d",&cas); while(cas--) { scanf("%d%d%d",&n,&m,&p); memset(F,0,sizeof(F));cnt=1; int a,b,c,d; for(int i=0;i<m;i++) { scanf("%d%d%d%d",&a,&b,&c,&d); add(a,b,d*p-c); } printf("Case %d: ",T++); solve(); } return 0; }