ACM学习之路___HDU 2066 一个人的旅行

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

9  
  一定要注意题中的细节(陷阱),a,b之间可能有多条路(输入时需处理),将草儿家记为 0, 一遍 dijkstra(),在判断草儿家到想去的地方所需时最短的那个就好,再就没什么了

  #include <iostream>
  #include <cstdio>
  #include <cstring>
  using namespace std;
  const int MAXINT=1<<25;
  int num0[1050][1050];
  int num1[1050];
  int dis[1050];//distance
  bool flag0[1050];
  int T,S,D,flag,MIN,m;
  void dijkstra()
  {
  memset(flag0,0,sizeof(flag0));//重置标记数组
  for(int i=0 ; i<=m ; i++)
    dis[i]=num0[0][i];//各点到草儿家所需最小时间
    flag0[0]=1;
    dis[0]=0;
  for(int i=0 ; i<m ; i++)
  {
    MIN=MAXINT;
    for(int j=1 ; j<=m ; j++)
    {
      if(dis[j]<MIN && !flag0[j])
      {
        MIN=dis[j];
        flag=j;
      }
    }
      if(MIN==MAXINT)
        break;
      flag0[flag]=1;
      for(int j=1 ; j<=m ; j++)
        if(!flag0[j])//attention
          dis[j]=min(dis[j],dis[flag]+num0[flag][j]);//各点到草儿家所需最短时间
  }
}
int main()
{
  int i,j,a,b,time,Min;
  while(~scanf("%d%d%d",&T,&S,&D))
  {
    m=-1;
    for(i=0 ; i<1050 ; i++)
      for(j=0 ; j<=i ; j++)
        if(i != j)
          num0[i][j]=num0[j][i]=MAXINT;
        else
          num0[i][j]=0;//点与点之间所需时间初始化
    for(i=0 ; i<T ; i++)
    {
      scanf("%d%d%d",&a,&b,&time);
        if(time<num0[a][b])//因为a,b间不止一条路,选取时间最短的那条
          num0[a][b]=num0[b][a]=time;
          m=max(max(m,a),b);
    }
    for(i=0 ; i<S ; i++)
    {

      int s;
      scanf("%d",&s);
      num0[0][s]=num0[s][0]=0;
    }
    for(i=0 ; i<D ; i++)
      scanf("%d",&num1[i]);
    dijkstra();
    Min=MAXINT;
    for(i=0 ; i<D ; i++)
      Min=min(Min,dis[num1[i]]);//想要到的地方中所需最小时间
    printf("%d\n",Min);
  }
return 0;
}

 
 
 
上一篇:Jquery 一些好用的插件和工具类


下一篇:Servlet基础(三) Servlet的多线程同步问题