2066.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 = 1; i <= n; i++)
    {
        dist[i] = length[a][i];
        s[i]    =        false;
    }
    dist[a] =    0;
    s[a]    = true;
    for(i = 1; i < n; i++)
    {
        int min = maxint;
        for(j = 1; j <= n; j++)
        {
            if(s[j] == false && (dist[j] < min))
            {
                min  = dist[j];
                u    =      j;
            }
        }
        if(min == maxint)
        {
            break;
        }
        s[u] = true;
        for(j = 1; j <= n; j++)
        {
            if(s[j] == false && length[u][j] < maxint && min + length[u][j] < dist[j])
            {
                dist[j] = min + length[u][j];
            }
        }
    }
    return dist[b] ;
}
int main()
{
    int t, s, d ,i, j, st, ed, temp, max, result, linked, wanted;
    while(scanf("%d %d %d", &t, &s, &d) == 3)
    {
        max = 0;
        for(i = 1; i < 1010; i++)
        {
            for(j = 1; j < 1010; j++)
            {
                length[i][j] = maxint;
            }
        }
        for(i = 0; i < t; i++)
        {
            scanf("%d %d %d", &st, &ed, &temp);
            if(length[st][ed] == maxint || (length[st][ed] != maxint && length[st][ed] > temp))
            {
                length[st][ed] = temp;
                length[ed][st] = temp;
                if(st > max)
                {
                    max = st;
                }
                if(ed > max)
                {
                    max = ed;
                }
            }
        }
        for(i = 0; i < s; i++)
        {
            scanf("%d", &linked);
            length[max + 1][linked] = 1;
            length[linked][max + 1] = 1;
        }
        for(i = 0; i < d; i++)
        {
            scanf("%d", &wanted);
            length[max + 2][wanted] = 1;
            length[wanted][max + 2] = 1;
        }
        printf("%d\n", Dijkstra(max + 1, max + 2, max + 2) - 2);
    }
    return 0;
}