首页 > 代码库 > noi 1997 最优乘车
noi 1997 最优乘车
H城是一个旅游胜地，每年都有成千上万的人前来观光。为方便游客，巴士公司在各个旅游景点及宾馆，饭店等地都设置了巴士站并开通了一些单程巴上线路。每条单程巴士线路从某个巴士站出发，依次途经若干个巴士站，最终到达终点巴士站。
一名旅客最近到H城旅游，他很想去S公园游玩，但如果从他所在的饭店没有一路已士
可以直接到达S公园，则他可能要先乘某一路巴士坐几站，再下来换乘同一站台的另一路巴士, 这样换乘几次后到达S公园。
现在用整数1,2,…N 给H城的所有的巴士站编号，约定这名旅客所在饭店的巴士站编号为1…S公园巴士站的编号为N。
写一个程序，帮助这名旅客寻找一个最优乘车方案,使他在从饭店乘车到S公园的过程
中换车的次数最少。
输入：
第一行有两个数字M和N(1<=M<=100 1<N<=500），表
示开通了M条单程巴士线路，总共有N个车站。从第二行到第M刊行依次给出了第1条到
第M条巴士线路的信息。其中第i+1行给出的是第i条巴士线路的信息，从左至右按运行顺序依次给出了该线路上的所有站号相邻两个站号之间用一个空格隔开。
输出：
只有一行。如果无法乘巴士从饭店到达S公园，则输出
"NO"，否则输出你的程序所找到的最少换车次数，换车次数为0表示不需换车即可到达?
输入部分比较麻烦..我每输一个数据就循环一次，这样可以把一条线路上的每个点的距离都赋值为1，遇到换行符就开始下一组..
然后用弗洛伊德跑一遍结果就出来了..
仍然没有删调试代码www
1 #include<iostream> 2 #include<cstring> 3 #include<algorithm> 4 #include<cstdio> 5 using namespace std; 6 int m,n,dis[510][510],f[510][510]; 7 void init() 8 { 9 cin>>m>>n;10 for(int i=1;i<=m;i++)11 {12 int a,y=0;13 char b=‘ ‘;14 while(b!=10)15 {16 cin>>a;17 b=getchar();18 f[i][++y]=a;19 for(int j=1;j<y;j++)20 {21 dis[f[i][j]][a]=1;22 //cout<<"!!!"<<f[i][j]<<‘ ‘<<a<<endl;23 }24 if(b==10) break;25 }26 }27 }28 int main()29 {30 memset(dis,10,sizeof(dis));31 memset(f,0,sizeof(f));32 init();33 for(int i=1;i<=n;i++) dis[i][i]=0;34 for(int k=1;k<=n;k++)35 for(int i=1;i<=n;i++)36 for(int j=1;j<=n;j++)37 if(dis[i][k]+dis[k][j]<dis[i][j])38 {39 /*cout<<"起点："<<i<<"中继: "<<k<<"终点: "<<j<<endl;40 cout<<dis[i][k]<<‘ ‘<<dis[k][j]<<endl;41 cout<<dis[i][j]<<endl;*/42 dis[i][j]=dis[i][k]+dis[k][j];43 //cout<<dis[i][j]<<endl<<endl;44 }45 46 if(dis[1][n]>10000) cout<<"NO"<<endl;47 else cout<<dis[1][n]-1<<endl;48 return 0;49 }
noi 1997 最优乘车
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。