首页 > 代码库 > CSU 1333 Funny Car Racing （最短路）
CSU 1333 Funny Car Racing （最短路）
题目链接： http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1333
解题报告：一个图里面有n个点和m条单向边，注意是单向边，然后每条路开a秒关闭b秒，问从s点到t点的最短时间。一个简单的最短路稍微变了一下。
卡了很久就因为没看到边是单向边，无语。可以用队列优化。
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 node10 {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 }
CSU 1333 Funny Car Racing （最短路）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。