本文主要是介绍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（最短路）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
