HDU 2066 一个人的旅行

一个人的旅行

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 7413 Accepted Submission(s): 2518

Problem Description

虽然草儿是个路痴（就是在杭电待了一年多，居然还会在校园里迷路的人，汗~),但是草儿仍然很喜欢旅行，因为在旅途中会遇见很多人（白马王子，^0^），很多事，还能丰富自己的阅历，还可以看美丽的风景……草儿想去很多地方，她想要去东京铁塔看夜景，去威尼斯看电影，去阳明山上看海芋，去纽约纯粹看雪景，去巴黎喝咖啡写信，去北京探望孟姜女……眼看寒假就快到了，这么一大段时间，可不能浪费啊，一定要给自己好好的放个假，可是也不能荒废了训练啊，所以草儿决定在要在最短的时间去一个自己想去的地方！因为草儿的家在一个小镇上，没有火车经过，所以她只能去邻近的城市坐火车（好可怜啊~）。

Input

输入数据有多组，每组的第一行是三个整数T，S和D，表示有T条路，和草儿家相邻的城市的有S个，草儿想去的地方有D个；
接着有T行，每行有三个整数a，b，time,表示a,b城市之间的车程是time小时；(1=<(a,b)<=1000;a,b 之间可能有多条路)
接着的第T+1行有S个数，表示和草儿家相连的城市；
接着的第T+2行有D个数，表示草儿想去地方。

Output

输出草儿能去某个喜欢的城市的最短时间。

Sample Input

6 2 3

1 3 5

1 4 7

2 8 12

3 8 4

4 9 12

9 10 2

1 2

8 9 10

Sample Output

这里加个超级源点，然后超级源点到原来的起点的权值赋为0

就变成单源最短路径了。

View Code

#include <iostream>
#include <cstring>
using namespace std;
const int INF = 1<<30;
int g[1100][1100];
int d[1100];
int used[1100];
int flag[1010];
void init(int n)
{
 int i, j;
 for (i = 0; i < n; i++)
 {
  d[i] = INF;
 }
 
 for (i = 0; i < n; i++)
 {
  for (j = 0; j < n; j++)
  {
   g[i][j] = INF;
  }
 }
 memset(used, 0, sizeof(used));
}
void F(int star, int n)
{
 d[star] = 0;
 int min, min_num;
 int i;
 for (int cnt = 0; cnt < n; cnt++)
 {
  min = INF;//////////////////////
  for (i = 0; i < n; i++)
  {
   if (!used[i] && min > d[i])
   {
    min = d[i];
    min_num = i;
   }
  }
  
  used[min_num] = 1;
  
  for (i = 0; i < n; i++)
  {
   if (!used[i] && d[i] > d[min_num] + g[min_num][i])
   {
    d[i] = d[min_num] + g[min_num][i];
   }
  }
 }
}
int main()
{
 int n, m, s, d1;//别和d[]重复。
 int i;
 while (cin >>m >> s >> d1)
 {
  init(1001);//看清楚总顶点数。别写成了n = s+d1+1。。。。题目共有1000个点，加上超级源点就是1001个点了。
  while (m--)
  {
   int a, b, c;
   cin >> a >> b>>c;
   if (c < g[a][b])
   {
    g[a][b] = g[b][a] = c;
   }
  }
  while (s--)
  {
   int a;
   cin >> a;
   g[0][a] = g[a][0] = 0;
  }
  int k = 0;
  while (d1--)
  {
   int a;
   cin >> a;
   flag[k++] = a;
  }
  
     F(0, 1001);
  
  int min = INF;
  for (i = 0; i < k; i++)
  {
   if (min > d[flag[i]])
   {
    min = d[flag[i]];
   }
  }
  cout << min << endl;
 }
 
 return 0;
}