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输入 #19 3 5 1 2 3 1 4 5 3 6 7 5 6 7 6 8 9输出 #14输入输出样例 #2输入 #215 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输出 #23说明/提示【样例解释#1】有两种方法从站台1 11走到站台9 991 ⇒ 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≤1051 ≤ K , M ≤ 1000 1\le K,M\le 10001≤K,M≤1000。【说明】本题分值按 COCI 原题设置满分120 120120。题目译自 COCI2012~2013 CONTEST#5T4 HIPERCIJEVI。C实现#includebits/stdc.h#defineINF0x7f7f7f7f#defineN500005usingnamespacestd;intvis[N],dis[N],n,k,m;vectorintg[N];intmain(){cinnkm;for(inti1;im;i)for(intj1;jk;j){intv;cinv;g[ni].push_back(v);//把每根管子表示成一个点g[v].push_back(ni);}queueintq;//BFS也可以是最短路memset(dis,0x7f,sizeofdis);q.push(1),vis[1]1,dis[1]1;while(!q.empty()){inttq.front();q.pop();if(tn)break;for(inti0;ig[t].size();i){intpg[t][i];if(!vis[p]){vis[p]1,dis[p]dis[t]1;q.push(g[t][i]);}}}if(dis[n]INF)cout-1;//无解的情况elsecoutdis[n]/21;//最短路/21return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容