首页 > 代码库 > POJ——T3259 Wormholes

POJ——T3259 Wormholes

2024-09-23 22:13:50   203人阅读

http://poj.org/problem?id=3259

Time Limit: 2000MS Memory Limit: 65536K
Total Submissions: 50692 Accepted: 18750

技术分享

 

发现虫洞的的JOhn~开始他的神秘之~~~~

就是给你m条带权双向边，w条带权单向边

可以将单边制成负的，SFPA求一下是否有负环

 

 1 #include <cstring> 2 #include <cstdio> 3  4 #define MIN(a,b) ( a<b ?a :b) 5  6 using namespace std; 7  8 const int N(2521); 9 int t,n,m,c,u,v,w;10 int head[N],sumedge;11 struct Edge12 {13     int to,next,cost;14     Edge(int to=0,int next=0,int cost=0):15         to(to),next(next),cost(cost){}16 }edge[N<<1];17 18 void ins(int from,int to,int cost)19 {20     edge[++sumedge]=Edge(to,head[from],cost);21     head[from]=sumedge;22 }23 24 int if_YES,vis[N],dis[N];25 26 void SPFA(int now)27 {28     vis[now]=1;29     if(if_YES) return ;30     for(int i=head[now];i;i=edge[i].next)31     {32         int go=edge[i].to;33         if(dis[go]>dis[now]+edge[i].cost)34         {35             if(vis[go])36             {37                 if_YES=1;38                 break;39             }40             dis[go]=dis[now]+edge[i].cost;41             SPFA(go);42         }43     }44     vis[now]=0;45 }46 47 void init()48 {49     if_YES=sumedge=0;50     memset(vis,0,sizeof(vis));51     memset(dis,0,sizeof(dis));52     memset(head,0,sizeof(head));53 }54 55 int main()56 {57     scanf("%d",&t);58     for(;t;t--)59     {    init();60         scanf("%d%d%d",&n,&m,&c);61         for(;m;m--)62         {63             scanf("%d%d%d",&u,&v,&w);64             ins(u,v,w); ins(v,u,w);65         }    66         for(;c;c--)67         {68             scanf("%d%d%d",&u,&v,&w);69             ins(u,v,-w);70         }71         for(int i=1;i<=n;i++)72         {73             SPFA(i);74             if(if_YES) break;75         }76         if(if_YES) printf("YES\n");77         else        printf("NO\n");78     }79     return 0;80 }

 

POJ——T3259 Wormholes


联系
我们