最少换乘 第八届
最少換乘
時(shí)間限制：2000?ms ?|? 內(nèi)存限制：65535?KB 難度：3 描述?歐洲某城是一個(gè)著名的旅游勝地，每年都有成千上萬(wàn)的人前來(lái)觀光旅行。Dr. Kong決定利用暑假好好游覽一番。。
年輕人旅游不怕辛苦，不怕勞累，只要費(fèi)用低就行。但Dr. Kong年過(guò)半百，他希望乘坐BUS從住的賓館到想去游覽的景點(diǎn)，期間盡可量地少換乘車(chē)。
?
Dr. Kon買(mǎi)了一張旅游地圖。他發(fā)現(xiàn)，市政部門(mén)為了方便游客，在各個(gè)旅游景點(diǎn)及賓館，飯店等地方都設(shè)置了一些公交站并開(kāi)通了一些單程線路。每條單程線路從某個(gè)公交站出發(fā)，依次途經(jīng)若干個(gè)站，最終到達(dá)終點(diǎn)站。
但遺憾的是，從他住的賓館所在站出發(fā)，有的景點(diǎn)可以直達(dá)，有的景點(diǎn)不能直達(dá)，則他可能要先乘某路BUS坐上幾站，再下來(lái)?yè)Q乘同一站的另一路BUS,?這樣須經(jīng)過(guò)幾次換乘后才能到達(dá)要去的景點(diǎn)。
?
為了方便，假設(shè)對(duì)該城的所有公交站用1，2，……，N編號(hào)。Dr. Kong所在位置的編號(hào)為1，他將要去的景點(diǎn)編號(hào)為N。
請(qǐng)你幫助Dr. Kong尋找一個(gè)最優(yōu)乘車(chē)方案,從住處到景點(diǎn)，中間換車(chē)的次數(shù)最少。
輸入接下來(lái)對(duì)每組測(cè)試數(shù)據(jù)：
第1行: M N 表示有M條單程公交線路，共有N站。（1<=M<=100 1<N<=500）
第2~M+1行： 每行描述一路公交線路信息，從左至右按運(yùn)行順序依次給出了該線路上的所有站號(hào)，相鄰兩個(gè)站號(hào)之間用一個(gè)空格隔開(kāi)。
AC代碼：
Dijkstra最短路算法就可以了
#include<iostream> #include<cstdio> #include<cstring> #define n 550 #define INF 0xFFFFFFF using namespace std; int s[n][n],dis[n],book[n]; int K,M,N; int main() {int i,j,k,t;char c[2*n+10];int a[n];int min,sum;while(cin>>K)while(K--){scanf("%d %d",&M,&N);for(i=1;i<=N;i++)for(j=1;j<=N;j++){if(i==j)s[i][j]=0;else s[i][j]=INF;}getchar();for(i=0;i<M;i++){t=0;gets(c);int p=strlen(c);for(j=0;j<p;j++){if(c[j]!=' '){sum=0;while(c[j]!=' '&&j<p){sum=sum*10+(c[j]-'0');j++;}a[t++]=sum;}}for(j=0;j<t;j++)for(k=j+1;k<t;k++)s[a[j]][a[k]]=1; }for(i=1;i<=N;i++) { dis[i]=s[1][i]; book[i]=0; } book[1]=1; for(i=1;i<=N;i++) { min=INF; for(j=1;j<=N;j++) if(!book[j] && dis[j]<min){ k=j; min=dis[j]; } book[k]=1; for(j=1;j<=N;j++) if(!book[j] && dis[k]+s[k][j]<dis[j]) dis[j]=dis[k]+s[k][j]; }if(dis[N]==INF)printf("NO\n");else printf("%d\n",dis[N]-1);}return 0; }
總結(jié)
- 上一篇： 【JEECG技术博文】JEECG表单配置
- 下一篇： 实战-Ueditor扩展二次开发