CSU 1333 Funny Car Racing （最短路）

时间：2023-03-09 16:01:40
CSU 1333 Funny Car Racing （最短路）

题目链接： http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1333

解题报告：一个图里面有n个点和m条单向边，注意是单向边，然后每条路开a秒关闭b秒，问从s点到t点的最短时间。一个简单的最短路稍微变了一下。

卡了很久就因为没看到边是单向边，无语。可以用队列优化。

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #include<vector>

 #include<deque>

 using namespace std;

 const int maxn = ;

 struct node

 {

     int v,a,b;

     int t;

 };

 vector<node> List[maxn];

 int ans[maxn];

 int visit[maxn],exist[maxn],n,m,s,t;

 int main()

 {

     int kase = ;

     while(scanf("%d%d%d%d",&n,&m,&s,&t)!=EOF)

     {

         for(int i = ;i <= n;++i)

         List[i].clear();

         int u1,v1,a1,b1,t1;

         for(int i = ;i <= m;++i)

         {

             scanf("%d%d%d%d%d",&u1,&v1,&a1,&b1,&t1);

             if(a1 < t1) continue;    //不可能通过的路，已经过滤掉了

             node t0;

             t0.v = v1;

             t0.a = a1;

             t0.b = b1;

             t0.t = t1;

             List[u1].push_back(t0);

         }

         for(int i = ;i <= n;++i)

         ans[i] = 0x7fffffff;

         memset(visit,,sizeof(visit));

         ans[s] = ;

         while()

         {

             int p = -,M = ;

             for(int i = ;i <= n;++i)

             if(visit[i] ==  && ans[i] < M)

             {

                 M = ans[i];

                 p = i;

             }

             visit[p] = ;

             if(p == -) break;

             for(int i = ;i < List[p].size();++i)

             if(visit[List[p][i].v] == )

             {

                 int lt = ans[p] % (List[p][i].a + List[p][i].b);

                 if(List[p][i].a - lt >= List[p][i].t)

                 ans[List[p][i].v] = min(ans[List[p][i].v],ans[p] + List[p][i].t);

                 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));

             }

         }

         printf("Case %d: %d\n",kase++,ans[t]);

     }

     return ;

 }

相关文章