hdu2066(多源多汇最短路)

题目链接：hdu2066

多源多汇,可以建立超级源点和终点

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int inf = 0xfffffff;
const int N = 1005;
int map[N][N],n;
int dis[N];
bool v[N];
void dijstra()
{
    memset(v, false, sizeof(v));
    int i,j;
    for(i = 0; i <= n; i ++)
    dis[i] = map[0][i];
    v[0] = true;
    for(i = 1; i <= n; i ++)
    {
        int minn = inf, pos;
        for(j = 0; j <= n; j ++)
        {
            if(!v[j] && dis[j] < minn)
            {
                minn = dis[j];
                pos = j;
            }
        }
        v[pos] = true;
        for(j = 0; j <= n; j ++)
        if(!v[j] && map[pos][j] < inf && dis[pos] + map[pos][j]  < dis[j])
        dis[j] = dis[pos] + map[pos][j];
    }
    printf("%d\n",dis[n]);
}
int main()
{
    int T,S,D,i,j;
    while(~scanf("%d%d%d",&T,&S,&D))
    {
        for(i = 0; i < N; i ++)
        for(j = 0; j < N; j ++)
        map[i][j] = inf;
        n = 0;
        int x, y, z;
        while(T--)
        {

            scanf("%d%d%d",&x,&y,&z);
            if(map[x][y] > z) map[x][y] = map[y][x] = z;
            if(n < x) n = x;
            if(n < y) n = y;
        }
        while(S--)
        {
            scanf("%d",&x);//0为超级源点
            map[0][x] = map[x][0] = 0;
        }
        n ++;//最大的城市编号加1，作为超级终点
        while(D--)
        {
            scanf("%d",&x);
            map[n][x] = map[x][n] = 0;//目的城市到超级终点的路程为0
        }
        dijstra();
    }
    return 0;
}

hdu2066(多源多汇最短路),布布扣,bubuko.com

hdu2066(多源多汇最短路)

原文：http://blog.csdn.net/jzmzy/article/details/21229207