1874.cpp

杭电 acm部分代码 有兴趣的可以下载 谢谢

#include<stdio.h>
#include<string.h>
const int maxint=0x7fffffff;
int length[1010][1010];
int Dijkstra(int a, int b, int n)
{
    int i, j, u;
    int dist[1010];
    bool s[1010];
    for(i = 0; i < n; i++)
    {
        dist[i] = length[a][i];
        s[i]    =        false;
    }
    dist[a] =    0;
    s[a]    = true;
    for(i = 0; i < n - 1; i++)
    {
        int min = maxint;
        for(j = 0; j < n; j++)
        {
            if(s[j] == false && (dist[j] < min))
            {
                min  = dist[j];
                u    =      j;
            }
        }
        if(min == maxint)
        {
            break;
        }
        s[u] = true;
        for(j = 0; j < n; j++)
        {
            if(s[j] == false && length[u][j] < maxint && min + length[u][j] < dist[j])
            {
                dist[j] = min + length[u][j];
            }
        }
    }
    if(dist[b] == maxint)
        return -1;
    return dist[b] ;
}
int main()
{
    int n, m, a, b, len, i, j;
    while(scanf("%d %d", &n, &m) == 2)
    {
        for(i = 0; i < n; i++)
            for(j = 0; j < n; j++)
                length[i][j] = maxint;
        while(m--)
        {
            scanf("%d %d %d", &a, &b, &len);
            if(length[a][b] == maxint || (length[a][b] != maxint && length[a][b] > len))
            {
                length[a][b] = len;
                length[b][a] = len;
            }
        }
        scanf("%d %d", &a, &b);
        printf("%d\n", Dijkstra(a, b, n));
    }
    return 0;
}