題意：
就是從各點到X的最短距離及從X到各點的最短距離和的最大值。
第一利用dijstra求出從X到各點的最短距離。
然后所有的邊反向，再進(jìn)行一次dijstra求X到各點的最短路徑。
第二次求出的最短路徑也就是各點到X的最短路徑，因為邊已經(jīng)反向，對于第二次從X到各點的最短路徑正是
原圖從各點到X的最短路徑。
#include<iostream>
#include<queue>
using namespace std;
const int INF=0x7fffffff/100;
int map[1001][1001]={0};
int d[1001]={0},N,M,X;
int dd[1001]={0};
bool f[1001];
void dijstra()
{
for(int i=1; i<=N; i++)
d[i]=INF;
d[X]=0;
memset(f,0,sizeof f);
for(int i=1; i<=N; i++)
{
int min=INF,u=0;
for(int j=1; j<=N; j++)
if(d[j]<min&&!f[j])
{
min=d[j];
u=j;
}
f[u]=true;
for(int j=1; j<=N; j++)
{
if(d[u]+map[u][j]<d[j])
d[j]=d[u]+map[u][j];
}
}
}
void traverse()
{
int temp;
for(int i=1; i<=N; i++)
for(int j=1; j<i; j++)
{
temp = map[i][j];
map[i][j]=map[j][i];
map[j][i]=temp;
}
}
int main()
{
cin>>N>>M>>X;
for(int i=1; i<=N; i++)
for(int j=1; j<=N; j++)
map[i][j]=INF;
for(int i=1,s,t,value; i<=M; i++)
{
cin>>s>>t>>value;
map[s][t]=value;
}
dijstra();
for(int i=1; i<=N; i++)
dd[i]=d[i];
traverse();
dijstra();
int max=0;
for(int i=1; i<=N; i++)
if(d[i]+dd[i]>max)max=d[i]+dd[i];
cout<<max<<endl;
system("pause");
return 0;
}