nyoj 1238 最少换乘（dijkstra）

描述

欧洲某城是一个著名的旅游胜地，每年都有成千上万的人前来观光旅行。Dr. Kong决定利用暑假好好游览一番。。

年轻人旅游不怕辛苦，不怕劳累，只要费用低就行。但Dr. Kong年过半百，他希望乘坐BUS从住的宾馆到想去游览的景点，期间尽可量地少换乘车。

 

Dr. Kon买了一张旅游地图。他发现，市政部门为了方便游客，在各个旅游景点及宾馆，饭店等地方都设置了一些公交站并开通了一些单程线路。每条单程线路从某个公交站出发，依次途经若干个站，最终到达终点站。

但遗憾的是，从他住的宾馆所在站出发，有的景点可以直达，有的景点不能直达，则他可能要先乘某路BUS坐上几站，再下来换乘同一站的另一路BUS, 这样须经过几次换乘后才能到达要去的景点。

 

为了方便，假设对该城的所有公交站用1，2，……，N编号。Dr. Kong所在位置的编号为1，他将要去的景点编号为N。

请你帮助Dr. Kong寻找一个最优乘车方案,从住处到景点，中间换车的次数最少。

输入

第一行： K 表示有多少组测试数据。（2≤k≤8） 接下来对每组测试数据： 第1行: M N 表示有M条单程公交线路，共有N站。（1<=M<=100 1<N<=500） 第2~M+1行： 每行描述一路公交线路信息，从左至右按运行顺序依次给出了该线路上的所有站号，相邻两个站号之间用一个空格隔开。

输出

对于每组测试数据，输出一行，如果无法乘坐任何线路从住处到达景点，则输出"N0"，否则输出最少换车次数，输出0表示不需换车可以直达。

样例输入

样例输出

2
NO

来源

第八届河南省程序设计大赛

题解：m行，每行先建立mp=1，然后跑dijkstra就好了

AC代码：

  1 #pragma comment(linker, "/STACK:1024000000,1024000000")
  2 #include<iostream>
  3 #include<cstdio>
  4 #include<cstring>
  5 #include<cmath>
  6 #include<math.h>
  7 #include<algorithm>
  8 #include<queue>
  9 #include<set>
 10 #include<bitset>
 11 #include<map>
 12 #include<vector>
 13 #include<stdlib.h>
 14 using namespace std;
 15 #define ll long long
 16 #define eps 1e-10
 17 #define MOD 1000000007
 18 #define N 10000
 19 #define NN 506
 20 #define inf 1<<26
 21 int m,n;
 22 char s[N];
 23 int mp[NN][NN];
 24 int a[N];
 25 void init(){
 26     for(int i=1;i<NN;i++){
 27         for(int j=1;j<NN;j++){
 28             if(i==j) mp[i][j]=0;
 29             else mp[i][j]=inf;
 30         }
 31     }
 32 }
 33 int dijkstra(int beg,int ent)
 34 {
 35     int vis[NN];
 36     int dis[NN];
 37     for(int i=0;i<NN;i++)
 38     {
 39         dis[i]=inf;
 40         vis[i]=0;
 41     }
 42     vis[beg]=1;
 43     dis[beg]=0;
 44     int x=n-1;
 45     while(x--)
 46     {
 47         for(int i=1;i<=n;i++)
 48         {
 49             if(mp[beg][i])
 50             {
 51                 
 52                 if(dis[i]>mp[beg][i]+dis[beg])
 53                   dis[i]=mp[beg][i]+dis[beg];
 54             }
 55         }
 56         int minn=inf;
 57         for(int i=1;i<=n;i++)
 58         {
 59             if(!vis[i] && minn>dis[i])
 60             {
 61                 minn=dis[i];
 62                 beg=i;
 63             }
 64         }
 65         vis[beg]=1;
 66     }
 67     //for(int i=1;i<=n;i++)
 68       // printf("--%d
",dis[i]);
 69     return dis[ent]==inf?-1:dis[ent];
 70 }
 71 int main()
 72 {
 73     int t;
 74     scanf("%d",&t);
 75     while(t--){
 76         init();
 77         //scanf("%d%d",&m,&n);
 78         cin>>m>>n;
 79         getchar();
 80         for(int i=0;i<m;i++){
 81             gets(s);
 82             int num=0;
 83             int len=strlen(s);
 84             for(int j=0;j<len;j++){
 85                 if(s[j]!=' '){
 86                     int sum=0;
 87                     while(s[j]!=' ' && j<len){
 88                         sum=sum*10+(s[j]-'0');
 89                         j++;
 90                     }
 91                     a[num++]=sum;
 92                 }
 93             }
 94             for(int j=0;j<num;j++){
 95                 for(int k=j+1;k<num;k++){
 96                     mp[a[j]][a[k]]=1;
 97                 }
 98             }
 99         }
100         
101     
102 
103         int ans=dijkstra(1,n);
104         if(ans==-1){
105             printf("NO
");
106         }else{
107             printf("%d
",ans-1);
108         }
109     }
110     return 0;
111 }

View Code