P7407 [JOI 2021 Final] ロボット 建虚点

· · 题解

Description

出门左转

教练原话：JOI Final=日本的NOIP？？（大雾）

Solution

大体思路：建虚点+最短路

1. 为什么要建虚点？

当你在一个点决策下一步时，决策会有很多种情况，虚点的作用就是让我们考虑到所有的这些情况。

2. 如何建立虚点？敲黑板敲黑板

首先考虑会有几种情况

这样说，十分空洞，看不懂先跳吧，后面还会讲。

插播一个性质：我们对边改颜色可以做到不对后来产生任何影响。

原因很显然，一共有 M 种颜色，只要我们想，是可以做到每一条边的颜色各不相同的。

放个图，更好理解。（为了表示颜色，只有手绘了，手残勿喷TAT）

蓝色是你现在在的点，红色是几个相同颜色的点，黑色是所谓的虚点。

声明一下，这题虚点连的边都是有向边，因为权值会不同。

  1. 建虚点，每一种颜色建一个虚点
  2. 当前点向虚点连边（蓝->黑），权值为0
  3. 虚点向出去的点连边（黑->红），权值为其他所有同色的边的权值之和
  4. 出去的点向虚点连边（红->黑），权值为0

解释：

走2，3两种边，实现了改变其他所有同色边的情况。

走4，3两种边，（4进3出）实现了刚才说的乱七八糟的情况，这里细讲一下。（这非常重要，个人认为这是本题最难的一部分了）

现在我们在一个红点，要进蓝点，并且出来的又是红点，出来的时候选择改变其他所有红边。既然出来的时候改变其他所有的红边，那么进来的那条边肯定也改掉了，可以改成一个进去不需要任何花费的边，出来的时候改变其他红边的权值，所以我们直接以0的花费走到虚点，在以该所有红边的花费走出来，就可以了。

好了，虚点建完了，跑dij吧。

code

#include<bits/stdc++.h>
#define N 1000010
#define int long long
using namespace std;
inline void read(int& x)
{
    x=0;int y=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')y=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    x=x*y;
}
int n,m;
struct Node{
    int to,nxt,w,col;
}e[N<<1];
int cnt,head[N];
inline void add(int u,int v,int col,int w)
{
    e[++cnt].col=col;e[cnt].nxt=head[u],e[cnt].to=v,e[cnt].w=w;
    head[u]=cnt;
}
int vis[N],num[N],sum[N],rt[N],tot,d[N];
struct node{
    int dis,id;
    bool operator<(const node& x)const{return dis>x.dis;}
    node(){}
    node(int d_,int id_){dis=d_,id=id_;}
};
priority_queue<node> q;
inline void dij()
{
    memset(d,0x3f,sizeof(d));
    d[1]=0;
    q.push(node(d[1],1));
    while(!q.empty())
    {
        int x=q.top().id;q.pop();
        if(vis[x])continue;vis[x]=1;
        for(int i=head[x];i;i=e[i].nxt)
        {
            int y=e[i].to,w=e[i].w;
            if(d[y]>d[x]+w)
            {
                d[y]=d[x]+w;
                q.push(node(d[y],y));
            }
        }
    }
}
signed main(){
//  freopen("robot.in","r",stdin);
//  freopen("robot.out","w",stdout);
    read(n),read(m);
    for(int i=1;i<=m;i++)
    {
        int x,y,z,zz;
        read(x),read(y),read(z),read(zz);
        add(x,y,z,zz),add(y,x,z,zz);
    }
    tot=n;
//-------------------重点分割线--------------------------- 
    //这一段是关于建虚点的 
    for(int x=1;x<=n;x++)
    {
        for(int i=head[x];i;i=e[i].nxt)
        {
            if(!e[i].col)continue;
            sum[e[i].col]+=e[i].w; 
            num[e[i].col]++;
            //sum表示同色点的权值和，num表示该颜色点有几个 
        }
        for(int i=head[x];i;i=e[i].nxt)
        {
            int y=e[i].to;
            if(!e[i].col)continue;
            if(num[e[i].col]==1)e[i].w=0;//仅一个，花费为0 
            else 
            {
                if(!rt[e[i].col])
                //2类边，蓝->黑 
                //rt记录了每一种颜色的虚点编号 
                {
                    rt[e[i].col]=++tot;
                    add(x,tot,0,0);
                }
                add(rt[e[i].col],e[i].to,0,sum[e[i].col]-e[i].w);
                //3类边，黑->红，权值为sum[e[i].col]-e[i].w 
                add(e[i].to,rt[e[i].col],0,0);
                //4类边，红->黑，权值为0 
            }
        }
        for(int i=head[x];i;i=e[i].nxt) 
        {
            rt[e[i].col]=sum[e[i].col]=num[e[i].col]=0;
        }
        //别忘了清空数组 
        //由于一个点的度数不会太大，所以直接改会比memset快一点 
    }
//-------------------重点分割线--------------------------- 
    dij();
    if(d[n]==0x3f3f3f3f3f3f3f3f)printf("-1\n");
    else printf("%lld\n",d[n]);
    return 0;
}