带返回路径的dijkstra boj1469

寻找饭店Submit: 182   Accepted:51Time Limit: 1000MS  Memory Limit: 65535KDescription
由 于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);
}