由 于Arsenal4要考tofel很忙很忙，于是就把出题的任务交给了Xdog和Jyc了。但Arsenal4答应请他们吃饭作为补偿。Arsenal4 给他们列了一个饭店的列表，加学校一共有N个地点，其标号为1到N，学校在第X号地点上。Jyc手里有一份北京的交通图，可以知道这些地点之间是否有路。 由于北京的交通十分糟糕，因此同一条路来回走用的时间可能是不一样的（也就是说给的道路的耗费时间是有向的）。从学校走到每个饭店并返回学校都有一个最短 时间，并保证用最短时间的策略走，Jyc现在想知道这些最短策略中的最大值是多少，这样才知道自己有没有足够时间可以不考虑远近选择任意的饭店。你能帮帮 他吗？
Input
第1行: 三个整数N(1 ≤ N ≤ 1000), M (1 ≤ M ≤ 100,000), 和 X (1 ≤ X ≤ N)
第2到M+1行:每行有三个整数A,B,T (1 ≤ T≤ 100)，表示从A号地点走到B号地点需要用T的时间。（记住时间是有向的）
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
可能往返的路线是不一样的。
数据保证从学校出发到任意饭店并返回学校的路都是存在的。
解法：
1. 最开始使用了一个O(n^3)的算法，即求出所有路径的最短路径，然后在求X-饭店-X的所有最短路径。
TLE
2. 先用dij求出X点的单源最短路径，然后转置存储路径信息的path[][]数组，在求一遍，这样就得到所有点到X的最短路径， O(n^2)!
注意上面转置路径的作法，很巧妙的作法！！
这个方法适用下列情况：
求从某一点出发，到达其他点然后返回。求出去并返回的最短路径的情况。
#include
#include
#define MAX_INT 0x7fffffff
int path[1010][1010], map[2][1010], processed[1010];
void init_single_source(int *map, int size, int source)
{
int i;
for (i=1 ; i<=size ; i++)
map[i] = MAX_INT;
map[source] = 0;
}
int extract_min(int *map, int size)
{
int i, min, min_index;
min = MAX_INT;
min_index = -1;
for (i=1 ; i<=size ; i++)
{
if (0 == processed[i] && map[i] < min)
{
min = map[i];
min_index = i;
}
}
processed[min_index] = 1;
return min_index;
}
void dijkstra(int *map, int size, int source)
{
int i, j, min_index;
memset(processed, 0, sizeof(processed));
init_single_source(map, size, source);
for (i=1 ; i<=size ; i++)
{
min_index = extract_min(map, size);
for (j=1 ; j<=size ; j++)
{
if (0 == path[min_index][j])
continue;
if (map[j] > map[min_index] + path[min_index][j])
{
map[j] = map[min_index] + path[min_index][j];
}
}
}
}
void reverse_path(int size)
{
int i, j, tmp;
for (i=1 ; i<=size ; i++)
{
for (j=i+1 ; j<=size ; j++)
{
tmp = path[i][j];
path[i][j] = path[j][i];
path[j][i] = tmp;
}
}
}
int main(int argc, char *argv[])
{
int N, M, X, i, j, k, a, b, t, min_index;
scanf("%d %d %d", &N, &M, &X);
for (i=0 ; i
scanf("%d %d %d", &a, &b, &t);
path[a][b] = t;
}
dijkstra(map[0], N, X);
/* 这里转置了path二维数组，这样求出来的就是反向路径 */
reverse_path(N);
dijkstra(map[1], N, X);
/* find max */
int max = 0;
for (i=1 ; i<=N ; i++)
{
if (MAX_INT == map[0][i] || MAX_INT == map[1][i] || 0 == map[0][i] || 0 == map[1][i])
continue;
if (map[0][i] + map[1][i] > max)
max = map[0][i] + map[1][i];
}
printf("%d\n", max);
}