CSU 1333 Funny Car Racing （最短路）

 1 #include<cstdio> 
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<vector>
 6 #include<deque>
 7 using namespace std;
 8 const int maxn = 400;
 9 struct node
10 {
11     int v,a,b;
12     int t;
13 };
14 vector<node> List[maxn];
15 
16 int ans[maxn];
17 int visit[maxn],exist[maxn],n,m,s,t;
18 int main()
19 {
20     int kase = 1;
21     while(scanf("%d%d%d%d",&n,&m,&s,&t)!=EOF)
22     {
23         for(int i = 1;i <= n;++i)
24         List[i].clear();
25         int u1,v1,a1,b1,t1; 
26         for(int i = 1;i <= m;++i)
27         {
28             scanf("%d%d%d%d%d",&u1,&v1,&a1,&b1,&t1);
29             if(a1 < t1) continue;    //不可能通过的路，已经过滤掉了  
30             node t0;
31             t0.v = v1;
32             t0.a = a1;
33             t0.b = b1;
34             t0.t = t1;
35             List[u1].push_back(t0);
36         }
37         for(int i = 1;i <= n;++i)
38         ans[i] = 0x7fffffff;
39         memset(visit,0,sizeof(visit));
40         ans[s] = 0;
41         while(1)
42         {
43             int p = -1,M = 200000000;
44             for(int i = 1;i <= n;++i)
45             if(visit[i] == 0 && ans[i] < M)
46             {
47                 M = ans[i];
48                 p = i;
49             }
50             visit[p] = 1;
51             if(p == -1) break;
52             for(int i = 0;i < List[p].size();++i)
53             if(visit[List[p][i].v] == 0)
54             {
55                 int lt = ans[p] % (List[p][i].a + List[p][i].b);
56                 if(List[p][i].a - lt >= List[p][i].t)
57                 ans[List[p][i].v] = min(ans[List[p][i].v],ans[p] + List[p][i].t);
58                 else ans[List[p][i].v] = min(ans[List[p][i].v],ans[p] + (List[p][i].a + List[p][i].b - lt + List[p][i].t));
59             }
60         }
61         printf("Case %d: %d\n",kase++,ans[t]);
62     }
63     return 0;
64 }