1722 最优乘车 1997年NOI全国竞赛
2018-06-27 10:00:47来源:未知 阅读 ()
1722 最优乘车
1997年NOI全国竞赛
H城是一个旅游胜地,每年都有成千上万的人前来观光。为方便游客,巴士公司在各个旅游景点及宾馆,饭店等地都设置了巴士站并开通了一些单程巴上线路。每条单程巴士线路从某个巴士站出发,依次途经若干个巴士站,最终到达终点巴士站。
一名旅客最近到H城旅游,他很想去S公园游玩,但如果从他所在的饭店没有一路巴士可以直接到达S公园,则他可能要先乘某一路巴士坐几站,再下来换乘同一站台的另一路巴士, 这样换乘几次后到达S公园。
现在用整数1,2,…N 给H城的所有的巴士站编号,约定这名旅客所在饭店的巴士站编号为1…S公园巴士站的编号为N。
写一个程序,帮助这名旅客寻找一个最优乘车方案,使他在从饭店乘车到S公园的过程中换车的次数最少。
输入文件是INPUT.TXT。文件的第一行有两个数字M和N(1<=M<=100 1<N<=500),表示开通了M条单程巴士线路,总共有N个车站。从第二行到第M刊行依次给出了第1条到第M条巴士线路的信息。其中第i+1行给出的是第i条巴士线路的信息,从左至右按运行顺序依次给出了该线路上的所有站号相邻两个站号之间用一个空格隔开。
输出文件是OUTPUT.TXT,文件只有一行。如果无法乘巴士从饭店到达S公园,则输出"N0",否则输出你的程序所找到的最少换车次数,换车次数为0表示不需换车即可到达。
3 7
6 7
4 7 3 6
2 1 3 5
2
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int a[510][510]; int map[510][510]; int cd[510]; int inf=0x7fffffff; int main() { for(int i=0;i<=501;i++) for(int j=0;j<=501;j++) map[i][j]=inf; //memset(map,0x7f,sizeof(map)); //for(int i=1;i<=) int n,m; //scanf("%d%d",&m,&n); cin>>m>>n; char p; for(int i=1;i<=m;i++) { int now=1; char p; while(1) { int bc=0;//储存结果 p=getchar(); while(p>='0'&&p<='9') { bc=bc*10+p-'0'; p=getchar(); } if(bc!=0) { a[i][now]=bc; now++; } if(p==' ') continue; if(p=='\n') { if(a[i][now-1]==0) continue; cd[i]=now; now=1; break; } } cd[i]--; } for(int k=1;k<=m;k++) { for(int i=1;i<=cd[k];i++) { for(int j=i+1;j<=cd[k];j++) { if(i==j) map[a[k][i]][a[k][j]]=0; else map[a[k][i]][a[k][j]]=1; } } } for(int k=1;k<=n;k++) { for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(map[i][k]!=inf&&map[k][j]!=inf&&((map[i][k]+map[k][j]!=0))) if(map[i][j]>map[i][k]+map[k][j]) { map[i][j]=map[i][k]+map[k][j]; } } } } if(map[1][n]==inf) { cout<<"NO"; } else { cout<<map[1][n]-1; } return 0; }
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int a[510][510]; int map[510][510]; int cd[510]; int inf=0x7fffffff; int main() { for(int i=0;i<=501;i++) for(int j=0;j<=501;j++) map[i][j]=inf; //memset(map,0x7f,sizeof(map)); //for(int i=1;i<=) int n,m; //scanf("%d%d",&m,&n); cin>>m>>n; char p; for(int i=1;i<=m;i++) { int now=1; char p; while(1) { int bc=0;//储存结果 p=getchar(); while(p>='0'&&p<='9') { bc=bc*10+p-'0'; p=getchar(); } if(bc!=0) { a[i][now]=bc; now++; } if(p==' ') continue; if(p=='\n') { if(a[i][now-1]==0) continue; cd[i]=now; now=1; break; } } cd[i]--; } for(int k=1;k<=m;k++) { for(int i=1;i<=cd[k];i++) { for(int j=i+1;j<=cd[k];j++) { if(i==j) map[a[k][i]][a[k][j]]=0; else map[a[k][i]][a[k][j]]=1; } } } for(int k=1;k<=n;k++) { for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(map[i][k]!=inf&&map[k][j]!=inf&&((map[i][k]+map[k][j]!=0))) if(map[i][j]>map[i][k]+map[k][j]) { map[i][j]=map[i][k]+map[k][j]; } } } } if(map[1][n]==inf) { cout<<"NO"; } else { cout<<map[1][n]-1; } return 0; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
下一篇:5971 打击犯罪
- pearls 2020-02-09
- 最优布线问题 2018-06-18
- 矩阵连乘最优解---动态规划 2018-06-17
- 1722 最优乘车 未完成 2018-06-17
- 1722 最优乘车 1997年NOI全国竞赛 2018-06-17
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash