题目描述
图灵杯个人赛就要开始了，蔡老板召集俱乐部各部门的部长开会。综合楼有N (1<=N<=1000)间办公室，编号1~N每个办公室有一个部长在工（mo）作（yu），其中X号是蔡老板的办公室，会议也将在X(1<=X<=N)号办公室举行。综合楼的构造极其特殊，这N个办公室之间M(1<=M<=100,000)条单向走廊。通过第i条路将需要花费Ti(1<=Ti<=100)单位时间。
由于工作很忙，开完会之后各部长需要返回自己的办公室。他们会选择最短时间的最优路径。
为了合理安排接下来的工作，蔡老板想知道，【来回最久的】【！！！】那个部长在路上花费的时间是多少。
输入
第一行：用空格隔开的三个数N，M和X
接下来的M行：每行有用空格隔开的三个数Ai，Bi和Ti，表示从A点到B点花费的时间Ti
输出
一个int型的数，表示花费时间的最大值
样例输入
4 4 1
1 2 1
2 3 1
3 4 3
4 1 3
样例输出
8
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
#define MAX 0xfffffff
using namespace std; int m,n,x;
int vis[];
int map1[][],dis1[];
int map2[][],dis2[]; void dijkstra1(int (*map)[],int *dis)
{
memset(vis,,sizeof(vis));
vis[x]=;
for(int i=;i<=n;i++)
{
dis[i]=map[x][i];
}
for(int i=;i<=n;i++)
{
int M=MAX,k=-;
for(int j=;j<=n;j++)
{
if(!vis[j]&&dis[j]<M)
M=dis[j],k=j;
}
if(k==-)
return;
vis[k]=;
for(int j=;j<=n;j++)
{
if(!vis[j]&&dis[j]>dis[k]+map[k][j])
dis[j]=dis[k]+map[k][j];
} }
} int main()
{
while(scanf("%d%d%d",&n,&m,&x)!=EOF)
{
//memset(vis,0,sizeof(vis));
for(int i=;i<=n;i++)
{
for(int j=;j<=n;j++)
map1[i][j]=map2[i][j]=i==j?:MAX;
}
for(int i=;i<=m;i++)
{
int a,b,t;
scanf("%d%d%d",&a,&b,&t);
if(map1[a][b]>t)
map1[a][b]=t;
if(map2[b][a]>t)
map2[b][a]=t;
}
dijkstra1(map1,dis1);
dijkstra1(map2,dis2);
for(int i=;i<=n;i++)
{
dis1[i]=dis1[i]+dis2[i];
}
sort(dis1+,dis1++n);
printf("%d\n",dis1[n]); }
return ;
}