(阶段三 dijkstra算法温习1.2)HDU 2066 一个人的旅行(使用dijkstra来解决多源起点和多源终点的最短路径问题)

/* 
 * HDU_2066.cpp 
 * 
 *  Created on: 2013年11月10日 
 *      Author: Administrator 
 */  
  
#include   
#include   
  
using namespace std;  
  
const int maxn = 1100;  
const int inf = 10000000;  
int map[maxn][maxn];  
int d[maxn];  
int s[maxn];  
int n,m;  
int from[maxn];  
int want[maxn];  
int ss;  
int dd;  
  
/** 
 * dijkstra算法用于有向加权图的最短路径问题 
 * 
 * 有一个大神总结的很好(至少我个人比较赞同..): 
 * 用最小生成树算法来求最小边权和 
 * 用dijkstra算法将所有的最小值都存起来 
 */  
int dijkstra(int v){//选择v作为源节点,利用dijkstra算法计算源节点v到各节点的最短路径  
    int i;  
    for(i = 1 ; i < 1050 ; ++i){//初始化  
        s[i] = 0;//s[i] = 0,表示i节点未被访问过  
        d[i] = map[v][i];//将d[i]定义为源节点v到节点i的最短距离  
    }  
  
    s[v] = 1;  
    d[v] = 0;  
    int j;  
    for(i = 1 ; i <1050 ; ++i){  
        int min = inf;  
        int pos;  
  
        for(j = 1 ; j <= 1050 ; ++j){  
            if(!s[j] && min > d[j]){  
                pos = j;  
                min = d[j];  
            }  
        }  
  
        s[pos] = 1;  
  
        for(j = 1 ; j <= 1050 ; ++j){  
            if(!s[j] && (d[j] > (d[pos] +map[pos][j]))){//如果j节点没有被访问过&&j节点到源节点的最短路径>pos节点到源节点的最短路径+pos节点到j节点的路径  
                d[j] = d[pos] + map[pos][j];//更新j节点到源节点的最短路径  
            }  
        }  
    }  
  
    /** 
     * 多源终点问题的核心代码: 
     * 取终点中的最小值 
     */  
    int min = inf;  
    for(i = 1 ; i <= dd ;++i){  
        if(min >





 d[want[i]]){  
            min = d[want[i]];  
        }  
    }  
    return min;//返回所要求的源节点到n节点的最短路径  
}  
  
int main(){  
    int t;  
    while(scanf("%d%d%d",&t,&ss,&dd)!=EOF){  
        int i,j;  
        for(i = 1 ; i <= 1050 ; ++i){  
            for(j = 1 ; j <= 1050 ; ++j){  
                map[i][j] = inf;  
            }  
        }  
  
        for(i = 1 ; i <= t ; ++i){  
            int a,b,time;  
            scanf("%d%d%d",&a,&b,&time);  
            if(map[a][b] > time){  
                map[a][b] = map[b][a] = time;  
            }  
        }  
  
        for(i = 1 ; i <= ss ; ++i){  
            scanf("%d",&from[i]);  
        }  
  
        for(i = 1 ; i <= dd ; ++i){  
            scanf("%d",&want[i]);  
        }  
  
        /** 
         * 多源起点问题的核心代码 
         */  
        int ans = inf;  
        for(i = 1 ; i <= ss ; ++i){  
            int temp = dijkstra(from[i]);  
            if(ans > temp){  
                ans = temp;  
            }  
        }  
  
        printf("%d\n",ans);  
    }  
    return 0;  
}