HDU - 2066 一个人的旅行（最短路径）

/*
Dijkstra单源最短路
权值必须是非负
单源最短路径，Dijkstra算法，邻接矩阵形式，复杂度为O(n^2)
求出源beg到所有点的最短路径，传入图的顶点数，和邻接矩阵cost[][]
返回各点的最短路径lowcost[]，路径pre[].pre[i]记录beg到i路径上的父结点，pre[beg]=-1
可更改路径权类型，但是权值必须为非负
*/
#include<iostream>
#include<stdio.h>
using namespace std;

const int MAXN=1010;
#define typec int
const typec INF=0x3f3f3f3f;//防止后面溢出，这个不能太大
bool vis[MAXN];
int pre[MAXN];
void Dijkstra(typec cost[][MAXN],typec lowcost[],int n,int beg){
    for(int i=0;i<n;i++){
        lowcost[i]=INF;vis[i]=false;pre[i]=-1;
    }
    lowcost[beg]=0;
    for(int j=0;j<n;j++){
        int k=-1;
        int Min=INF;
        for(int i=0;i<n;i++)
            if(!vis[i]&&lowcost[i]<Min){
                Min=lowcost[i];
                k=i;
            }
        if(k==-1)break;
        vis[k]=true;
        for(int i=0;i<n;i++)
            if(!vis[i]&&lowcost[k]+cost[k][i]<lowcost[i]){
                lowcost[i]=lowcost[k]+cost[k][i];
                pre[i]=k;
            }
    }
}

int cost[MAXN][MAXN];
int lowcost[MAXN];

int main(){

    int T,S,D;
    int a,b,time;
    int city1[MAXN];
    int city2[MAXN];

    while(~scanf("%d%d%d",&T,&S,&D)){
        for(int i=0;i<MAXN;++i){
            for(int j=0;j<MAXN;++j){
                cost[i][j]=INF;
            }
        }

        for(int i=0;i<T;++i){
            scanf("%d%d%d",&a,&b,&time);
            if(time<cost[a][b]){
                cost[a][b]=time;
                cost[b][a]=time;
            }
        }
        //0作为草儿家
        for(int i=0;i<S;++i){
            scanf("%d",&city1[i]);
            cost[0][city1[i]]=0;
            cost[city1[i]][0]=1;
        }
        for(int i=0;i<D;++i){
            scanf("%d",&city2[i]);
        }

        Dijkstra(cost,lowcost,MAXN,0);
        int minTime=lowcost[city2[0]];
        for(int i=1;i<D;++i){
            if(lowcost[city2[i]]<minTime)
                minTime=lowcost[city2[i]];
        }

        printf("%d\n",minTime);
    }
    return 0;
}