ARC061E-solution

igAC · 2023-07-25 14:30:01 · 题解

\text{Describe}

洛谷 link

ATlink

简要题意（洛谷翻译）：

Snuke 的城镇有地铁行驶，地铁线路图包括 n 个站点和 m 个地铁线。站点被从 1 到 n 的整数所标记，每条线路被一个公司所拥有，并且每个公司用彼此不同的整数来表示。

第 i 条线路（1 \le i \le m）是直接连接 p_i 与 q_i 的双向铁路，中间不存在其他站点，且这条铁路由 c_i 公司所拥有。

如果乘客只乘坐同一公司的铁路，他只需要花费一元，但如果更换其他公司的铁路需要再花一元。当然，如果你要再换回原来的公司，你还是要花一元。

Snuke 在 1 号站的位置出发，他想通过地铁去第 n 站，请求出最小钱数。如果无法到达第 n 站，输出 -1。

\text{Solution}

\text{Sol1}

不难想到拆点，我们将每个点拆成与每个公司的铁路相连的点，每个拆出来的点只与公司编号相同的点相连（语文烂，轻喷）。

将 1 号站点拆成 (1,1)，每个由 1 号公司运营的铁路与它相连。

如 1 3 1 就将 (1,1) 与 (3,1) 相连。

每条铁路最多新增加 2 个节点，节点个数不会超过 2m。

接下来考虑如何转线，若每个节点都连向相邻的结点的话，边数会达到 O(m^2)，我们接受不了。

对于图论来说，复杂度不对的话，可以考虑建虚点。----沃兹基烁德

我们可以对每个站点新建一个 0 号节点，站点拆出来的点都向 0 号节点连一条费用为 0 的边，0 号节点向其他点连费用为 1 的边。

这样就很好的处理了转线的问题，而且边数降到了 O(m)。

接下来在这张图上以 (1,0) 为起点，(n,0) 为终点跑最短路（Dijkstra，SPFA，01BFS 均可），就可得出答案。

\text{Sol2}

考虑为什么直接 01BFS 跑出来的答案是错误的，如下例：

01BFS 只考虑 dis_{to}>dis_{now}+w 的情况。

若我们先遍历 1 \to 2 \to 4 这一条路，那么 dis_{4}=1，而 1 \to 3 \to 4 则不会被考虑。

而对于 4 \to 5 的转移，我们发现 1 \to 3 \to 4 是更优的，但是我们将它忽略了。

所以我们需要多考虑 dis_{to}=dis_{now}+w 的情况。

我们可以对每个节点都维护一个 set，每次转移的时候在 set 中查找是否有与当前路公司相同的。

对于 dis_{to}=dis_{now}+w 的情况，我们就将 col[now][to] 加入 to 的集合中。

对于 dis_{to}>dis_{now}+w 的情况，显然公司是否相同是不重要的，直接花费 1 的代价转线是不劣于从相同公司转移过来的。

于是就将 set 清空，重新加入公司编号。

在最短路转移的时候考虑以上两种情况，就可得出答案。

具体实现可参考代码。

\text{Code}

\text{Code1}

#include<bits/stdc++.h>
#define LLINF 1e18
#define int long long
#define N 200005
#define M 1000005
using namespace std;
int read(){
    int x=0,f=1,ch=getchar();
    for(;!isdigit(ch);ch=getchar()) f=(ch=='-')?-1:1;
    for(;isdigit(ch);ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
    return x*f;
}
int n,m,dis[M],tot;
map<int,vector<int>>mp[N];
map<int,int>bel[M];
vector<int>col[M],p[M];
vector<pair<int,int>>g[M];
void add_edge(int x,int y,int z){g[x].push_back({y,z});}
void BFS(int s){
    for(int i=1;i<=tot;++i) dis[i]=LLINF;
    deque<int>q;
    dis[s]=0,q.push_front(s);
    while(!q.empty()){
        int x=q.front();q.pop_front();
        for(auto [y,z]:g[x]){
            if(!z){
                if(dis[y]>dis[x]){
                    dis[y]=dis[x];
                    q.push_front(y);
                }
            }
            else{
                if(dis[y]>dis[x]+1){
                    dis[y]=dis[x]+1;
                    q.push_back(y);
                }
            }
        }
    }
    if(dis[p[n][0]]==LLINF) puts("-1");
    else printf("%lld",dis[p[n][0]]);
}
signed main(){
    n=read(),m=read();
    for(int i=1;i<=m;++i){
        int x=read(),y=read(),z=read();
        mp[x][z].push_back(y);
        mp[y][z].push_back(x);
        col[x].push_back(z);
        col[y].push_back(z);
    }
    for(int i=1;i<=n;++i) col[i].push_back(0);
    for(int i=1;i<=n;++i){
        sort(col[i].begin(),col[i].end());
        col[i].erase(unique(col[i].begin(),col[i].end()),col[i].end());
        for(int x:col[i]){
            p[i].push_back(++tot);
            bel[i][x]=tot;
        }
    }
    for(int i=1;i<=n;++i){
        for(int j=1;j<col[i].size();++j){
            add_edge(p[i][j],p[i][0],0);
            add_edge(p[i][0],p[i][j],1);
            for(int x:mp[i][col[i][j]]) add_edge(p[i][j],bel[x][col[i][j]],0);
        }
    }
    BFS(p[1][0]);
    return 0;
}

\text{Code2}

#include<bits/stdc++.h>
#define LLINF 1e18
#define int long long
#define N 100005
using namespace std;
int read(){
    int x=0,f=1,ch=getchar();
    for(;!isdigit(ch);ch=getchar()) f=(ch=='-')?-1:1;
    for(;isdigit(ch);ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
    return x*f;
}
int head[N],tot,n,m,dis[N];
bool vis[N];
struct Edge{
    int to,nxt;
    int c;
}e[N<<2];
void add_edge(int x,int y,int c){
    e[++tot].to=y;
    e[tot].c=c;
    e[tot].nxt=head[x];
    head[x]=tot;
}
set<int>vis_col[N];
int val(int x,int c){return (vis_col[x].find(c)==vis_col[x].end());}
void SPFA(){
    for(int i=1;i<=n;++i) dis[i]=LLINF;
    queue<int>q;
    dis[1]=0,vis[1]=true,q.push(1);
    while(!q.empty()){
        int x=q.front();q.pop();
        vis[x]=false;
        for(int i=head[x];i;i=e[i].nxt){
            int y=e[i].to,c=e[i].c,w=val(x,c);
            if(dis[y]>dis[x]+w){
                dis[y]=dis[x]+w;
                if(!vis[y]){
                    q.push(y);
                    vis[y]=true;
                }
                vis_col[y].clear();
                vis_col[y].insert(c);
            }
            else if(dis[y]==dis[x]+w){
                if(val(y,c)){
                    if(!vis[y]){
                        q.push(y);
                        vis[y]=true;
                    }
                    vis_col[y].insert(c);
                }
            }
        }
    }
    if(dis[n]==LLINF) puts("-1");
    else printf("%lld",dis[n]);
}
signed main(){
    n=read(),m=read();
    for(int i=1;i<=m;++i){
        int x=read(),y=read(),c=read();
        add_edge(x,y,c);
        add_edge(y,x,c);
    }
    SPFA();
    return 0;
}