poj-3259 Wormholes(无向、负权、最短路)

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

 

Description

While exploring his many farms, Farmer John has discovered a number of amazing wormholes. A wormhole is very peculiar because it is a one-way path that delivers you to its destination at a time that is BEFORE you entered the wormhole! Each of FJ's farms comprises N (1 ≤ N ≤ 500) fields conveniently numbered 1..NM (1 ≤ M ≤ 2500) paths, and W (1 ≤ W ≤ 200) wormholes.

As FJ is an avid time-traveling fan, he wants to do the following: start at some field, travel through some paths and wormholes, and return to the starting field a time before his initial departure. Perhaps he will be able to meet himself :) .

To help FJ find out whether this is possible or not, he will supply you with complete maps to F (1 ≤ F ≤ 5) of his farms. No paths will take longer than 10,000 seconds to travel and no wormhole can bring FJ back in time by more than 10,000 seconds.

Input

Line 1: A single integer, FF farm descriptions follow. 
Line 1 of each farm: Three space-separated integers respectively: NM, and W 
Lines 2..M+1 of each farm: Three space-separated numbers (SET) that describe, respectively: a bidirectional path between S and E that requires T seconds to traverse. Two fields might be connected by more than one path. 
Lines M+2..M+W+1 of each farm: Three space-separated numbers (SET) that describe, respectively: A one way path from S to E that also moves the traveler back T seconds.

Output

Lines 1..F: For each farm, output "YES" if FJ can achieve his goal, otherwise output "NO" (do not include the quotes).

Sample Input

2
3 3 1
1 2 2
1 3 4
2 3 1
3 1 3
3 2 1
1 2 3
2 3 4
3 1 8

Sample Output

NO
YES

Hint

For farm 1, FJ cannot travel back in time. 
For farm 2, FJ could travel back in time by the cycle 1->2->3->1, arriving back at his starting location 1 second before he leaves. He could start from anywhere on the cycle to accomplish this.  

题目大意:

时空旅行,前m条路是双向的,旅行时间为正值,w条路是虫洞,单向的,旅行时间是负值,也就是能回到过去。求从一点出发,判断能否在”过去“回到出发点,即会到出发点的时间是负的。

解题思路:

裸的负权最短路问题,SPAF Bellman-Ford解决。

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 #define INF 0x3f3f3f3f
 5 #define N 10100
 6 int nodenum, edgenum, w, original=1; //点,边,起点
 7 
 8 typedef struct Edge //边
 9 {
10     int u;
11     int v; 
12     int cost;
13 }Edge;//边的数据结构
14 
15 Edge edge[N];//边
16 
17 int dis[N];//距离
18 
19 bool Bellman_Ford()
20 {
21     for(int i = 1; i <= nodenum; ++i) //初始化
22         dis[i] = (i == original ? 0 : INF);
23     int F=0; 
24     for(int i = 1; i <= nodenum - 1; ++i)//进行nodenum-1次的松弛遍历
25     {
26         for(int j = 1; j <= edgenum*2+w; ++j)
27         {
28             if(dis[edge[j].v] > dis[edge[j].u] + edge[j].cost) //松弛(顺序一定不能反~)
29             {
30                 dis[edge[j].v] = dis[edge[j].u] + edge[j].cost;
31                 F=1;
32             }
33         }
34         if(!F)
35             break;
36     }    
37         //与迪杰斯特拉算法类似,但不是贪心!
38         //并没有标记数组
39         //本来松弛已经结束了
40         //但是因为由于负权环的无限松弛性
41         bool flag = 1; //判断是否含有负权回路
42         //如果存在负权环的话一定能够继续松弛
43         for(int i = 1; i <= edgenum*2+w; ++i)
44         {
45             if(dis[edge[i].v] > dis[edge[i].u] + edge[i].cost)
46             {
47                 flag = 0;
48                 break;
49             }
50         }
51         //只有在负权环中才能再松弛下去
52     return flag;
53 }
54 
55 int main()
56 {
57     int t;
58     scanf("%d",&t);
59     while(t--)
60     {
61         
62         scanf("%d %d %d", &nodenum, &edgenum, &w);
63 
64         for(int i = 1; i <= 2*edgenum; i+=2)//加上道路,双向边 
65         {
66             scanf("%d %d %d", &edge[i].u, &edge[i].v, &edge[i].cost);
67             edge[i+1].u=edge[i].v;
68             edge[i+1].v=edge[i].u;
69             edge[i+1].cost=edge[i].cost;
70         }
71         for(int i =2*edgenum+1; i <= 2*edgenum+w; i++)//加上虫洞,单向边,负权 
72         {
73             scanf("%d %d %d", &edge[i].u, &edge[i].v, &edge[i].cost);
74             edge[i].cost=-edge[i].cost;
75         }
76         if(Bellman_Ford())//没有负环 
77             printf("NO\n");
78         else
79             printf("YES\n");
80     }
81     return 0;
82 }

 

     
上一篇:USACO Building Roads


下一篇:动物农场 Animal Farm【读后思】