题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=2066
dijkstra函数每执行一次,得到的dis数组存储的是起点s到其他所有点的距离
需要执行s次函数,每次函数分别求出到想去的点的距离的最小值
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
const int N = 1200;
const int INF = 0x3f3f3f3f;
int map[N][N], dis[N], vis[N], from[N], want[N], t, s, d;
int dijkstra(int s)
{memset(vis, 0, sizeof(vis));for(int i = 0; i < N; i++)dis[i] = INF;dis[s] = 0;int _min, pos;for(int i = 0; i < N; i++){_min = INF;for(int j = 0; j < N; j++){if(!vis[j] && _min > dis[j]){pos = j;_min = dis[j];}}vis[pos] = 1;for(int j = 0; j < N; j++)if(!vis[j] && map[pos][j] + dis[pos] < dis[j])dis[j] = map[pos][j] + dis[pos];}_min = INF;for(int i = 0; i < d; i++)_min = min(_min, dis[want[i]]);return _min;
}
int main(void)
{
// freopen("1.txt", "r", stdin);
// freopen("2.txt", "w", stdout);while(scanf("%d%d%d", &t, &s, &d) != EOF){for(int i = 0; i < N; i++)for(int j = 0; j < N; j++)map[i][j] = INF;int a, b, time;for(int i = 0; i < t; i++){scanf("%d%d%d", &a, &b, &time);if(map[a][b] > time)map[a][b] = map[b][a] = time;}for(int i = 0; i < s; i++)scanf("%d", &from[i]);for(int i = 0; i < d; i++)scanf("%d", &want[i]);int _min = INF;for(int i = 0; i < s; i++)_min = min(_min, dijkstra(from[i]));printf("%d\n", _min);}return 0;
}