ABC277E 题解

· · 题解

题外话

此题我赛时没做出来，赛后被别人一句话搞懂。

做法

我们把题意略微转化一下：

给定两种类型的边，类型分别为 1，0。
你只能行走在你状态对应的边上。 例如你的状态是 1，就只能走在类型为 1 的边上。
现在有一些节点作为开关。可以在那里切换状态。
问从 1 走到 n 的最短路。

看到有两种边，而且这两种边互不兼容。
而且有开关可以在两种边上切换。
现在瓶颈就在于如何选择是否切换状态。
那么是不是可以将这个“选择”变成一条权值为 0 的边，来进行切换。
而现在有了代表是否选择切换的边，而原图上无法直接从一种边走到另一种边。
可以考虑把两种边分别建图。
而这个代表切换状态的边就是两个图之间的连边。

也就是分层图这个东西。

对种类为 1 的边，所连节点编号为 1 到 n。
对于种类为 0 的边，所连节点编号为 n+1 到 2n。
对于有开关的节点，设其为 u，则连接 u 和 u+n。

节点 n+1 到 2n 可以认为是编号为 1 到 n 节点的另一种状态，只不过由于状态不同，这些节点无法通过普通的边，只能通过代表状态切换的边与编号为 1 到 n 互通。

建完图之后跑最短路就行了。

Code

#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
int head[maxn*2];
struct EDGE
{
    int to,val,nxt;
}edge[maxn*4];
int cnt;
void add(int u,int to,int val)
{
    edge[++cnt].to=to;
    edge[cnt].val=val;
    edge[cnt].nxt=head[u];
    head[u]=cnt;
}
int n,m,k;
bool vis[maxn*2];
int dis[maxn*2];
void dijkstra()
{
    memset(dis,0x3f3f3f3f,sizeof dis);
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> que;
    que.push(make_pair(0,1));
    dis[1]=0;
    while(!que.empty())
    {
        int u=que.top().second;
        que.pop();
        if(vis[u])continue;
        vis[u]=1;
//      printf("u: %d\n",u);
        for(int i=head[u];i;i=edge[i].nxt)
        {
            int to=edge[i].to;
            if(dis[to]>dis[u]+edge[i].val)
            {
                dis[to]=dis[u]+edge[i].val;
            //  printf("dis[%d]: %d dis[%d]: %d\n",u,dis[u],to,dis[to]);
                que.push(make_pair(dis[to],to));
            }
        }
    }
    int ans=min(dis[n],dis[n*2]);
    if(ans==0x3f3f3f3f)printf("-1");
    else printf("%d",ans);
}
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    int u,v,a;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&u,&v,&a);
        if(a)
        {
            add(u,v,1);
            add(v,u,1);
        }
        else
        {
            add(u+n,v+n,1);
            add(v+n,u+n,1);
        }
    }
    int si;
    for(int i=1;i<=k;i++)
    {
        scanf("%d",&si);
        add(si,si+n,0);
        add(si+n,si,0);
    }
    dijkstra();
    return 0;
}