• 题目1238

最少换乘

时间限制：

2000 ms  |  内存限制：

65535 KB

难度：

3

描写叙述

 欧洲某城是一个著名的旅游胜地，每年都有成千上万的人前来观光旅行。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表示不需换车能够直达。

例子输入

23 76 74 7 3 62 1 3 52 61 3 5 2 6 4 3

例子输出

2NO

来源

上传者

记得竞赛的时候 我一直对队友说 这道题 你们能做，最后还是没做出来。对于刚刚接触acm的我dfs,bfs仅仅知道用

却不知道原理  今天大概一个小时 就做出来了

起初用的dfs做的 结果超时  就想着优化 结果还是没优化出来 

就用bfs了。。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;vector
          
           map[505];bool vis[505][505];int Min;struct List{ int data; struct List *next;};struct node{ int x,cost; friend bool operator <(node a,node b) { return a.cost>b.cost; }};int bfs(int pos,int key){ priority_queue
           
            s; node temp,temp1; temp.x=pos,temp.cost=0; while(!s.empty()) s.pop(); s.push(temp); while(!s.empty()) { temp=temp1=s.top(); s.pop(); if(temp.x==key) return temp.cost; for(int i=0;i
            
             ='0'&&str[i]<='9') x=x*10+str[i]-'0'; else if(x!=0) { List *temp; p->data=x; temp=(struct List *)malloc(sizeof(struct List)); p->next=temp; p=temp; x=0; } } p->next=NULL; p=head; for(p=head;p->next!=NULL;p=p->next) { for(List *l=p->next;l->next!=NULL;l=l->next) { map[p->data].push_back(l->data); } } while(head) { List *t; t=head->next; free(head); head=t; } p=head=(struct List *)malloc(sizeof(struct List)); } int x=bfs(1,n); if(x!=-1) printf("%d\n",x-1); else printf("NO\n"); } return 0;}