P7646 [COCI 2012/2013 #5] HIPERCIJEVI
题目描述
在遥远的星系中，最快的运输方式是超级管道，它们将K KK个站台连接在一起。从站台1 11到达站台N NN最少需要经过多少个站台?
输入格式
第一行，三个整数N , K , M N,K,MN,K,M，分别表示站台数，每根超级管道连接的站台数和超级管道数。
接下来M MM行，每行K KK个正整数，表示这跟超级管道连接的站台编号。
输出格式
一行，一个正整数，表示最少需要经过的站台数，如果到达不了站台N NN，则输出-1。
输入输出样例 #1
输入 #1
9 3 5 1 2 3 1 4 5 3 6 7 5 6 7 6 8 9输出 #1
4输入输出样例 #2
输入 #2
15 8 4 11 12 8 14 13 6 10 7 1 5 8 12 13 6 2 4 10 15 4 5 9 8 14 12 11 12 14 3 5 6 1 13输出 #2
3说明/提示
【样例解释#1】
有两种方法从站台1 11走到站台9 99：
1 ⇒ 3 ⇒ 6 ⇒ 9 1\Rightarrow 3\Rightarrow 6\Rightarrow 91⇒3⇒6⇒9或1 ⇒ 5 ⇒ 6 ⇒ 9 1\Rightarrow 5\Rightarrow 6\Rightarrow 91⇒5⇒6⇒9
共经过了4 44个站台，可以证明这是经过站台最少的情况。
【数据范围】
对于100 % 100\%100%的数据，1 ≤ N ≤ 10 5 1\le N\le 10^51≤N≤105，1 ≤ K , M ≤ 1000 1\le K,M\le 10001≤K,M≤1000。
【说明】
本题分值按 COCI 原题设置，满分120 120120。
题目译自 COCI2012~2013 CONTEST#5T4 HIPERCIJEVI。
C++实现
#include<bits/stdc++.h>#defineINF0x7f7f7f7f#defineN500005usingnamespacestd;intvis[N],dis[N],n,k,m;vector<int>g[N];intmain(){cin>>n>>k>>m;for(inti=1;i<=m;i++)for(intj=1;j<=k;j++){intv;cin>>v;g[n+i].push_back(v);//把每根管子表示成一个点g[v].push_back(n+i);}queue<int>q;//BFS，也可以是最短路memset(dis,0x7f,sizeofdis);q.push(1),vis[1]=1,dis[1]=1;while(!q.empty()){intt=q.front();q.pop();if(t==n)break;for(inti=0;i<g[t].size();i++){intp=g[t][i];if(!vis[p]){vis[p]=1,dis[p]=dis[t]+1;q.push(g[t][i]);}}}if(dis[n]==INF)cout<<-1;//无解的情况elsecout<<dis[n]/2+1;//最短路/2+1return0;}后续
接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容
)
