| Time Limit: 2000MS | Memory Limit: 65536K | |
| Total Submissions: 13489 | Accepted: 6075 |
Description
One cow from each of N farms (1 ≤ N ≤ 1000) conveniently numbered 1..N is going to attend the big cow party to be held at farm #X (1 ≤ X ≤ N). A total of M (1 ≤ M ≤ 100,000) unidirectional
(one-way roads connects pairs of farms; road i requires Ti (1 ≤ Ti ≤ 100) units of time to traverse.
Each cow must walk to the party and, when the party is over, return to her farm. Each cow is lazy and thus picks an optimal route with the shortest time. A cow's return route might be different from her original route to the party since roads are one-way.
Of all the cows, what is the longest amount of time a cow must spend walking to the party and back?
Input
Lines 2..M+1: Line i+1 describes road i with three space-separated integers: Ai, Bi, and Ti. The described road runs from farm Ai to farm Bi,
requiring Ti time units to traverse.
Output
Sample Input
4 8 2 1 2 4 1 3 2 1 4 7 2 1 1 2 3 5 3 1 2 3 4 4 4 2 3
Sample Output
10
Hint
Source
题目大意：
说的是有N个农场，每个农场出一个奶牛去第x个农场参加派对，i个弄农场到i+1个农场有一个距离，先求出每个奶牛从自己的农场出来后到达x个农场参加party再返回自己所在的农场的最短路，然后在这些最短的里面找到最大的一条。
解题思路：
其实就是Dijkstra的简单应用不过要注意的是，数据太大，用O（n3）的Floyd会T，所以呢，只要用两次Dijkstra就可以了，第一次以x为源点，求出其余的n-1个农场到达x的最短路，然后，再将edge[i][j]的行和列相互互换位置，就得到了n-1个农场到第x个农场的距离，然后再用一次Dijkstra，求出了第n-1个农场到第x个农场的距离，然后求他们的和的最大值就OK了。
代码：
# include<cstdio>
# include<iostream>
# include<cstring>
using namespace std;
# define MAX 1000+4
# define inf 99999999
int edge[MAX][MAX];
int book[MAX];
int dis[MAX];
int bdis[MAX];
int n,m,x;
int u,v;
void init()
{
for ( int i = 1;i <= n;i++ )
{
for ( int j = 1;j <= n;j++ )
{
if ( i==j )
{
edge[i][j] = 0;
}
else
{
edge[i][j] = inf;
}
}
}
}
void input()
{
for ( int i = 1;i <= m;i++ )
{
int t1,t2,t3;
cin>>t1>>t2>>t3;
edge[t1][t2] = t3;
}
}
int Dijkstra()
{
for ( int i = 1;i <= n;i++ )
{
book[i] = 0;
dis[i] = edge[x][i];
bdis[i] = edge[i][x];
}
int _min;
book[x] = 1;
for ( int i = 1;i <= n-1;i++ )
{
_min = inf;
for ( int j = 1;j <= n;j++ )
{
if ( book[j]==0&&dis[j] < _min )
{
_min = dis[j];
u = j;
}
}
book[u] = 1;
for ( v = 1;v <= n;v++ )
{
if ( book[v]==0&&dis[v] > dis[u]+edge[u][v] )
{
dis[v] = dis[u]+edge[u][v];
}
}
}
memset(book,0,sizeof(book));
book[x] = 1;
for ( int i = 1;i <= n;i++ )
{
_min = inf;
for ( int j = 1;j <= n;j++ )
{
if ( book[j]==0 && bdis[j] < _min )
{
_min = bdis[j];
u = j;
}
}
book[u] = 1;
for ( v = 1;v <= n;v++ )
{
if ( book[v]==0&&bdis[v] > bdis[u]+edge[v][u] )
{
bdis[v] = bdis[u]+edge[v][u];
}
}
}
_min = -1;
for ( int i = 1;i <= n;i++ )
{
if ( bdis[i]+dis[i] > _min )
{
_min = bdis[i]+dis[i];
}
}
return _min;
}
int main(void)
{
cin>>n>>m>>x;
init();
input();
printf("%d\n",Dijkstra());
return 0;
}