「JOI 2021 Final」机器人
首先走一条路且有其他路的颜色与这条路相同，有两种情况。
- 把这条路道路的颜色改变
- 把其他与这条路颜色相同的路的颜色改变。
又因为我们有 \(M\) 种颜色，一共只有 \(M\) 条路，所以我们可以做到将一条边涂改成一种独一无二的颜色。
由于重复经过一个点不可能成为最优方案，所以我们可以直接这么建边跑一段最短路。
但是这么跑出来的答案是偏大的。因为假设我们通过 \(1\) 方式转移，那么下一次走相同颜色的边就可以少改变一条边的颜色。
而如果通过 \(2\) 方式转移，则没有影响，因为如果通过 \(2\) 方式改变边的颜色会对之后产生影响的话，不如直接走会产生影响的那条边，这样更优。
所以我们还得建边，对于点 \(u,v\)，我们要新建边来满足这样的需求：从 \(u\) 走颜色为 \(c\) 的边到 \(v\)，然后在 \(v\) 接着走颜色为 \(c\) 的边，并且从 \(u\) 到 \(v\) 是通过 \(1\) 方式，从 \(v\) 走出是通过 \(2\) 方式。
建好新边后再跑一遍最短路就行了，我们可以采用虚点的策略去建新边，那么点数不超过 \(n+2\times m\)，边数不超过 \(6\times m\)。
代码如下：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 6e5+5;
const ll INF = 1e17;
int n,m;
ll dis[MAXN],cnt[MAXN];
struct E
{
int to;ll w;int c;
};
vector <E> g[MAXN],e[MAXN];
struct node
{
int p;ll dis;
bool operator < (const node&x)const
{
return dis>x.dis;
}
};
bool vis[MAXN];
void dij()
{
memset(dis,0x3f,sizeof dis);
memset(vis,0,sizeof vis);
priority_queue <node> q;
q.push(node{1,0});
dis[1]=0;
while(!q.empty())
{
node now=q.top();
q.pop();
int p=now.p;
if(vis[p]) continue;
vis[p]=1;
for(int i=0;i<e[p].size();++i)
{
int to=e[p][i].to;ll w=e[p][i].w;
if(dis[to]>dis[p]+w)
{
dis[to]=dis[p]+w;
q.push(node{to,dis[to]});
}
}
}
if(dis[n]>INF) printf("-1\n");
else printf("%lld\n",dis[n]);
}
map <int,int> mp[MAXN];
void dfs(int p)
{
vis[p]=1;
for(int i=0;i<g[p].size();++i)
cnt[g[p][i].c]+=g[p][i].w;
for(int i=0;i<g[p].size();++i)
{
int to=g[p][i].to;
e[p].push_back(E{to,cnt[g[p][i].c]>g[p][i].w?min(g[p][i].w,cnt[g[p][i].c]-g[p][i].w):0,0});
e[p].push_back(E{mp[to][g[p][i].c],0,0});
e[mp[p][g[p][i].c]].push_back(E{to,cnt[g[p][i].c]-g[p][i].w,0});
}
for(int i=0;i<g[p].size();++i)
cnt[g[p][i].c]=0;
for(int i=0;i<g[p].size();++i)
{
int to=g[p][i].to;
if(vis[to]) continue;
dfs(to);
}
}
int main()
{
// freopen("robot.in","r",stdin);
// freopen("robot.out","w",stdout);
scanf("%d %d",&n,&m);
int Node=n;
for(int i=1;i<=m;++i)
{
int u,v,c;ll p;
scanf("%d %d %d %lld",&u,&v,&c,&p);
g[u].push_back(E{v,p,c});
g[v].push_back(E{u,p,c});
if(!mp[u].count(c)) mp[u][c]=++Node;
if(!mp[v].count(c)) mp[v][c]=++Node;
}
dfs(1);
dij();
return 0;
}