hdu 2066一人旅(dijkstra複数起点と終点)
1980 ワード
テーマリンク:http://acm.hdu.edu.cn/showproblem.php?pid=2066
dijkstra関数は一回実行するごとに、得られたdis配列は起点sから他のすべての点までの距離を格納します.
s次関数を実行する必要があります.それぞれの関数で行きたいポイントまでの距離の最小値を求めます.
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
", _min);
}
return 0;
}