首页 > 代码库 > ACdream 1198 Transformers' Mission(最短路)
ACdream 1198 Transformers' Mission(最短路)
题目地址:http://acdream.info/problem?pid=1198
比赛的时候做出的人很少。。。所以我也没看。。。。其实就是一道简单的最短路。。。要使时间最短,那么对于每一个点来说都要最短的时间从起点走到该点,然后再用最短的时间从该点到终点,那么只要求两次最短路就行了。然后最后求两个最短路的和的最大值,即最晚到达的时间。
代码如下:
#include <iostream> #include <cstdio> #include <string> #include <cstring> #include <stdlib.h> #include <math.h> #include <ctype.h> #include <queue> #include <map> #include <set> #include <algorithm> using namespace std; const int INF=0x3f3f3f3f; int d[2][2000], vis[2000], n, head[2000], cnt; struct node { int u, v, w, next; }edge[1000000]; void add(int u, int v, int w) { edge[cnt].v=v; edge[cnt].w=w; edge[cnt].next=head[u]; head[u]=cnt++; } void spfa(int x, int source) { memset(vis,0,sizeof(vis)); queue<int>q; q.push(source); d[x][source]=0; while(!q.empty()) { int u=q.front(); q.pop(); vis[u]=0; for(int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].v; if(d[x][v]>d[x][u]+edge[i].w) { d[x][v]=d[x][u]+edge[i].w; if(!vis[v]) { vis[v]=1; q.push(v); } } } } } int main() { int t, i, m, s, e, num=0, u, v, w; scanf("%d",&t); while(t--) { num++; scanf("%d%d",&n,&m); memset(head,-1,sizeof(head)); cnt=0; while(m--) { scanf("%d%d%d",&u,&v,&w); add(u,v,w); add(v,u,w); } scanf("%d%d",&s,&e); memset(d,INF,sizeof(d)); spfa(0,s); spfa(1,e); /*for(i=0;i<n;i++) { printf("%d %d\n",d[0][i],d[1][i]); }*/ int max1=-1; for(i=0;i<n;i++) { if(max1<d[0][i]+d[1][i]) max1=d[0][i]+d[1][i]; } printf("Case #%d: %d\n",num,max1); } return 0; }
ACdream 1198 Transformers' Mission(最短路)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。