dijkstra boj1231

SnowSubmit: 507   Accepted:215Time Limit: 1000MS  Memory Limit: 65536KDescription
2008年1月，中国南方遭受了百年难遇的大雪灾其时间持续之长，雪势之大是我们无法想象得到的。大雪给那里人们的生活，工作，生产带来了极大的不便。为了抗击雪灾，需要从一些城市紧急调运一些生活物资到灾区。

Input
第一行是两个整数 交通枢纽数N （2<=N<=1024）， 和路径的条数M（1<=M<=10000）
接下来M 行 每行3个整数 a， b ， t ， 表示由城市a到城市b需要的时间t ( 1<=t<=1024)
最后一行是两个整数 s， t 分别表示源城市和目的城市


Output
输出一个整数 ，从s到t的最短时间

Sample Input

4 5
1 2 5
1 3 3
2 3 1
2 4 3
3 4 6
1 4


Sample Output

7


dijkstra算法(回路，正权边，单源最短路径)

#include <iostream>
#include <vector>
using namespace std;

#define MAX_INT 0x7fffffff;

int map[1500];
int processed[1500];
int path[10001][10001];
int N, M, a, b, t;

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

/*抽取最小值位置，已使用的需要做标记*/
int extract_min(int *map, int size)
{
    int i, min = MAX_INT;
    int min_index;
    for (i=1 ; i<=size ; i++)
    {
        if (map[i] < min && 0 == processed[i])
        {
            min = map[i];
            min_index = i;
        }
    }
    processed[min_index] = 1;
    return min_index;
}

int main(int argc, char *argv[])
{
    int i, j, min_index;
    scanf("%d", &N);
    scanf("%d", &M);

    for (i=0 ; i<M ; i++)
    {
        scanf("%d %d %d ", &a, &b, &t);
        path[a][b] = t;
        path[b][a] = t;
    }
    scanf("%d %d", &a, &b);
   
    init_single_source(map, N, a);
    /*release*/
    for (i=1 ; i<=N ; i++)
    {
        min_index = extract_min(map, N);
        for (j=1 ; j<=N ; j++)
        {
            if (0 != path[min_index][j])
            {
                if (map[min_index] + path[min_index][j] < map[j])
                {
                    map[j] = map[min_index] + path[min_index][j];
                }
            }
        }
    }
    cout << map[b] << endl;
}