dijkstra boj1734 百度地图

百度地图Submit: 76   Accepted:27Time Limit: 2000MS  Memory Limit: 65536KDescription
newstar 想去饭店大吃一顿，用baidu地图查找周围饭店分布情况，baidu地图给他列了一个饭店的列表，加学校一共有N个地点，其标号为1到N，学校在第1号 地点上。从百度地图上可以知道这些地点之间是否有路。由于北京的交通十分糟糕，因此同一条路来回走用的时间可能是不一样的（也就是说给的道路的耗费时间是 有向的）。从学校走到每个饭店并返回学校都有一个最短时间，并保证用最短时间的策略走，newstar只去一个饭店，现在想知道去哪个饭店所花时间最小， 并且最小值是多少？

Input
多组数据
第1行: 三个整数N(1 ≤ N ≤ 1000), M (1 ≤ M ≤ 100,000)；
第2到M+1行:每行有三个整数A,B,T (1 ≤ T≤ 100)，表示从A号地点走到B号地点需要用T的时间。（记住时间是有向的）
饭店号码从1，2，3，...,N;


Output
每组数据输出一行，只有两个整数，中间隔着一个空格。输出饭店号码和最优往返用时最短耗费时间。


Sample Input

4 8
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

3 4

解题思路：
可以用单源最短路径来做。
计算出1-N的所有单源最短路径，然后根据所有单源最短路径信息计算出1-n(n属于1-N)-1的路径中的最小值

可以用dijkstra来求单源最短路径,使用数组来实现，extract_min可以用c++的最小优先级队列来实现，这里为了代码实现的简单，就采用了数组的方式。(其实我不是很熟悉c++的pqueue，改天把她搞定)

#include 
#include 

#define MAX_INT 0x7fffffff

int N, M;
/* map[i]记录了i结点到其他结点的最短距离，
   path[i][j]记录结点i到结点j的距离,
   processed[i]记录了在使用dijkstra的过程中，i结点是否已计算过
 */
int path[1010][1010], map[1010][1010], processed[1010];

void init_single_source(int *map, int size, int src)
{
    int i;
    for (i=1 ; i    {
        map[i] = MAX_INT;
    }
    map[src] = 0;
}

/* 采用遍历的方式寻找最小值， 低效，但是简单 -_-!*/
int extract_min(int *map, int size)
{
    int i, min = MAX_INT;
    int min_index;
    for (i=1 ; i    {
        if (map[i] < min && 0 == processed[i])
        {
            min = map[i];
            min_index = i;
        }
    }
    processed[min_index] = 1;
    return min_index;
}

void clear_data()
{
    memset(path, 0, sizeof(path));
    memset(map, 0, sizeof(map));
}

int main(int argc, char *argv[])
{
    int i, j, k, src, des, distance, min_index ,ret_min;
    while (EOF != scanf("%d %d", &N, &M))
    {
        clear_data();
        for (i=0 ; i        {
            scanf("%d %d %d", &src, &des, &distance);
            path[src][des] = distance;
        }
        for (k=1 ; k        {
            memset(processed, 0, sizeof(processed));
            init_single_source(map[k], N, k);
            /* do release, 路径的release操作 */
            for (i=1 ; i<=N ; i++)
            {
                min_index = extract_min(map[k], N);
                for (j=1 ; j<=N ; j++)
                {
                    if (0 != path[min_index][j])
                    {
                        if (map[k][min_index] + path[min_index][j] < map[k][j])
                            map[k][j] = map[k][min_index] + path[min_index][j];
                    }
                }
            }
        }
        /* find min path */
        ret_min = MAX_INT;
        des = 1;
        for (i=1 ; i        {
            if (MAX_INT == map[1][i] || 0 == map[1][i] || MAX_INT == map[i][1] || MAX_INT == map[i][1])
                continue;
            if (map[1][i] + map[i][1] < ret_min)
            {
                ret_min = map[1][i] + map[i][1];
                des = i;
            }
        }
        printf("%d %d\n", des, ret_min);
    }
}