首页 > ACM题库 > HDU-杭电 > hdu 2066 一个人的旅行-Dijkstra-[解题报告]C++
2013
12-29

hdu 2066 一个人的旅行-Dijkstra-[解题报告]C++

一个人的旅行

问题描述 :

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

输入:

输入数据有多组,每组的第一行是三个整数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个数,表示草儿想去地方。

输出:

输入数据有多组,每组的第一行是三个整数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个数,表示草儿想去地方。

样例输入:

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

样例输出:

9

点击打开链接hdu 2066


思路:最短路+Dijkstra
分析:题目给定的起点有s个,终点有d个。要求找到从起点到这些终点最短的路径。很显然只要枚举起点然后比较最后得到最小的值。

代码:

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
#define MAXN 1010
#define INF 0xFFFFFFF

int t , s , d;
int sCity[MAXN];
int dCity[MAXN];
int dis[MAXN];
int vis[MAXN];
int value[MAXN][MAXN];

void init(){
   for(int i = 1 ; i < MAXN ; i++){
      for(int j = 1 ; j < MAXN ; j++)
        value[i][j] = INF;
   }
}

void Dijkstra(int s){
    int pos;
    memset(vis , 0 , sizeof(vis));
    for(int i = 1 ; i < MAXN; i++)
       dis[i] = INF;
    dis[s] = 0;
    for(int i = 1 ; i < MAXN ; i++){
       pos = -1;
       for(int j = 1 ; j < MAXN ; j++){
          if(!vis[j] && (pos == -1 || dis[j] < dis[pos]))
            pos = j;
       } 
       if(pos == -1)
          break;
       vis[pos] = 1;
       for(int j = 1 ; j < MAXN ; j++){
          if(!vis[j] && dis[j] > dis[pos] + value[pos][j])
            dis[j] = dis[pos] + value[pos][j];
       }
    }
}

int main(){
   int a , b , v , ans;
   while(scanf("%d%d%d" , &t , &s , &d) != EOF){
      init();
      for(int i = 0 ; i < t ; i++){
         scanf("%d%d%d" , &a , &b , &v);
         if(value[a][b] > v)
           value[a][b] = value[b][a] = v;
      }
      for(int i = 0 ; i < s ; i++)
         scanf("%d" , &sCity[i]);
      for(int i = 0 ; i < d ; i++)
         scanf("%d" , &dCity[i]);
      ans = INF;
      /*枚举起点*/
      for(int i = 0 ; i < s ; i++){
         Dijkstra(sCity[i]);
         for(int j = 0 ; j < d ; j++)/*枚举终点*/
            ans = ans < dis[dCity[j]] ? ans : dis[dCity[j]];
      }
      printf("%d\n" , ans);
   }
   return 0;
}

解题转自:http://blog.csdn.net/chenguolinblog/article/details/8045301


  1. 如果两个序列的最后字符不匹配(即X [M-1]!= Y [N-1])
    L(X [0 .. M-1],Y [0 .. N-1])= MAX(L(X [0 .. M-2],Y [0 .. N-1]),L(X [0 .. M-1],Y [0 .. N-1])
    这里写错了吧。

  2. 我没看懂题目
    2
    5 6 -1 5 4 -7
    7 0 6 -1 1 -6 7 -5
    我觉得第一个应该是5 6 -1 5 4 输出是19 5 4
    第二个是7 0 6 -1 1 -6 7输出是14 7 7
    不知道题目例子是怎么得出来的

  3. I go through some of your put up and I uncovered a good deal of expertise from it. Many thanks for posting this sort of exciting posts