题解 P7646 【[COCI2012-2013#5] HIPERCIJEVI】

· · 题解

P7646 题解

Description

一根超级管道能够将 K 个站台连接在一起。求从站台 1 到达站台 N 最少需要经过多少个站台。

Solution

最短路裸题。

考虑将一根所谓的 m 个“超级管道”变成 m 个连接了 k 个点的点，那么转化之后就是裸的最短路问题了。

看到目前为止其他两篇题解讲的答案需要 dis[n]/2+1 都不是很清楚，这里再讲一遍：

先看一下一个“超级管道”连接 2 个点的情况，根据题意我们显然可以看作：

但是，照着我们的思路，我们会把它变成：

原本 1 \rightarrow 2 的路径会被拆成 1 \rightarrow 3 \rightarrow 2，也就是说我们求出的最短路径实际上是原来的 2 倍。如果把 1 \rightarrow n 的最短路记作 dis[n]，那么原来的最短路径就是 \dfrac{dis[n]}{2}。

因为要求的是点数，所以答案是 \dfrac{dis[n]}{2}+1。

最后的话这题卡空间不能开 long long，开了 long long 你就会和我一样提交了若干遍最后两个点 \color{white}\colorbox{#052242}{MLE}。

Code

inline void bfs(){
    memset(dst,-1,sizeof dst);
    queue<int> q;dst[1]=1;
    q.push(1);
    while(!q.empty()){
        int u=q.front();q.pop();
        for(int i=hd[u];i;i=es[i].nxt){
            int v=es[i].to;
            if(dst[v]==-1){
                dst[v]=dst[u]+1;
                q.push(v);
            }
        }
    }
}
int main(){
    n=read(),k=read(),m=read();
    for(int i=1;i<=m;i++)
        for(int j=1;j<=k;j++){
            int x=read();
            add(n+i,x),add(x,n+i);
        }
    bfs();
    writeln(dst[n]==-1?-1:dst[n]/2+1);
    return 0;
}