【AtCoder Regular Contest 061 E】Snuke's Subway Trip | Mrsrz's blog

最短路。

题目大意：

给定一张 $n$ 个点 $m$ 条边的无向图，每条边有一个所属的公司。

一个人连续走过同一家公司的边，只需要花费 $1$ 的代价。

问从 $1$ 走到 $n$ 的最少代价。

题解：

我们对同一家公司形成的连通块建一个虚点，每个点向这个虚点连权值为 $1$ 的边，然后跑最短路即可。

注意边权只有 $1$，所以可以直接 BFS。

由于每个连通块花费了 $2$ 的代价，所以最后答案除以 $2$ 即可。

最短路部分时间复杂度 $O(n)$。

找连通块时，每次选一条边，钦定这条边的公司，直接 dfs 找与其连通的结点即可。注意每次找的时候，不要重复经过点，否则复杂度错误。

Code：

#include<iostream>
#include<queue>
#include<map>
using namespace std;
const int N=2e6+6;
int n,m,cnt,nod;
map<int,int>head[N/10];
bool vis[N],vss[N];
struct Edge{
    int to,nxt,id,c;
}e[N];
namespace graph{
    struct edge{
        int to,nxt;
    }e[N];
    int head[N],cnt,dep[N];
    queue<int>q;
    inline void addedge(int u,int v){
        e[++cnt]=(edge){v,head[u]},head[u]=cnt;
        e[++cnt]=(edge){u,head[v]},head[v]=cnt;
    }
    int work(){
        dep[1]=1;
        for(q.push(1);!q.empty();){
            int u=q.front();q.pop();
            for(int i=head[u];i;i=e[i].nxt)
            if(!dep[e[i].to]){
                dep[e[i].to]=dep[u]+1;
                q.push(e[i].to);
            }
        }
        return dep[n]?dep[n]/2:-1;
    }
    void clear(int u){
        for(int i=head[u];i;i=e[i].nxt)vss[e[i].to]=0;
    }
}
void dfs(int now,int c){
    vss[now]=1;
    graph::addedge(nod,now);
    for(int i=head[now][c];i;i=e[i].nxt)if(!vis[e[i].id]){
        vis[e[i].id]=1;
        if(!vss[e[i].to])dfs(e[i].to,c);
    }
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;nod=n;
    for(int i=1;i<=m;++i){
        int u,v,c;
        cin>>u>>v>>c;
        e[++cnt]=(Edge){v,head[u][c],i,c},head[u][c]=cnt;
        e[++cnt]=(Edge){u,head[v][c],i,c},head[v][c]=cnt;
    }
    for(int i=1;i<=cnt;i+=2)if(!vis[e[i].id]){
        ++nod;
        dfs(e[i].to,e[i].c);
        graph::clear(nod);
    }
    cout<<graph::work()<<'\n';
    return 0;
}