成都网站建设冠辰,西安抖音运营,模板网站建设教程,传媒公司商业计划书最好的车 Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other) Total Submission(s) : 18 Accepted Submission(s) : 6 Problem Description H城是一个旅游胜地。每年都有成千上万的人前来观光。为方便游客。巴士公司在各个旅游景点及宾馆、… 最好的车 Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other) Total Submission(s) : 18 Accepted Submission(s) : 6 Problem Description H城是一个旅游胜地。每年都有成千上万的人前来观光。为方便游客。巴士公司在各个旅游景点及宾馆、饭店等地都设置了巴士站并开通了一些单程巴士线路。每条单程巴士线路从某个巴士站出发。依次途径若干个巴士站。最后到达终点巴士站。 一名旅客近期到H城旅游他非常想其S公园游玩。但假设从他所在的饭店没有一路巴士能够直接到达S公园则他可能要先乘某一路巴士坐几站再下来换乘同一站台的还有一路巴士这样换乘几次后到达S公园。 如今用整数1,2,...N给H城的全部的巴士站编号。约定这名旅客所在饭店的巴士站编号为1S公园巴士站的编号为N。 写一个程序。帮助这名旅客寻找一个最优乘车方案使他在从饭店乘车到S公园的过程中换车的次数最少。 Input 有多组输入数据每组数据的第一行有两个数字M和N(1M100 1N500)表示开通了M条单程巴士线路总共同拥有N个车站。从第2行到第M1行依次给出了第1条到第M条巴士线路的信息。当中第i1行给出的是第i条巴士线路的信息从左至右按执行顺序依次给出了该线路上的全部站号相邻两个站号之间用一个空格隔开。 Output 对于每组数据输出仅仅有一行。假设无法乘巴士从饭店到达S公园。则输出“NO”。否则输出你的程序所找到的最少换车次数换车次数为0,表示不需换车就可以到达。 Sample Input 3 7
6 7
4 7 3 6
2 1 3 5 Sample Output 2 基本的还是对数据的处理一个巴士线路上的站都仅仅要乘一次就到了那么我们建立图假设i网站和j网站同一时候出如今一个巴士线路上就连一条边他们之间的权值为1.然后用最短路处理dijkstra和floyed都能处理 #include iostream #include sstream #include string #include stdio.h #define MAX 100000099 #define Q 501 using namespace std; void dijkstra(int); int num[Q], a[Q][Q], dist[Q]; int main() { int M, N; while(cin M N) { for(int i 1; i N; i) { for(int j 1; j N; j) a[i][j]MAX; dist[i]MAX; } getchar(); int len, x; string str; for (int i 0; i M; i) { getline(cin,str); stringstream in(str); len 0; while(in x) num[len] x; for (int j 1; j len; j) for (int k j1; k len; k) a[num[j]][num[k]] 1; } /*for (int i 0; i N; i) { for (int j 0; j N; j) cout a[i][j] \t; cout endl; }*/ dijkstra(N); if(dist[N] MAX) cout NO endl; else cout dist[N]-1 endl; } } void dijkstra(int n) { //s[N]为标记 int s[Q],newdist,i; for(i1;in;i) { dist[i]a[1][i]; s[i]0; } dist[1]0; s[1]1; for(i2;in;i) { //找出离初始位置最小的点 int j,temMAX; int u1; for(j2;jn;j) if(!s[j]dist[j]tem) { uj; temdist[j]; } s[u]1; //更新dist[N]的值 for(j2;jn;j) { if(!s[j]a[u][j]MAX) { newdistdist[u]a[u][j]; if(newdistdist[j]) dist[j]newdist; } } } } 版权声明本文博客原创文章博客未经同意不得转载。
