noip模拟赛多校第八场 T3 遥控机器人（最短路 + 技巧拆点）

本文主要是介绍noip模拟赛多校第八场 T3 遥控机器人（最短路 + 技巧拆点），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题面

在这里插入图片描述

简要题意：
给你一个 $n$ 个点 $m$ 条边的图。边 $i$ 有颜色 $c_i$ 。你可以选择一些边改变它们的颜色成为区间 $[1, m]$ 中的任意颜色，改变一条边 $i$ 一次的代价是 $w_i$ 。询问你能否在一些改变操作后使得可以从 $1$ 号点，每次只经过当前点的 特殊边 到达 $n$ 。特殊边的定义是 对于当前点而言，特殊边的颜色在该点所有出边中有且仅出现一条。如果可以，输出最小代价。否则输出 $- 1$ 。

分析:

凭感觉是一道最短路的题。

首先有一个性质：因为颜色的区间与边数相同，所以如果要改变一条边，那么可以把它变成一个任何别的边都不会再变成的颜色。换言之， 如果要花费代价改变某一条边的颜色，那么可以把它变成无色，并且这样是最优的。

接下来我们考虑如果一条边 $(u, v)$ 的颜色是 $c$ ，花费是 $w$ 。我们从 $u$ 到 $v$ 经过它花费代价有几种情况：

1. $u$ 的出边中是 $c$ 颜色的只有一条，那么代价是 $0$ 。

2. $u$ 的出边中 $c$ 颜色的边有多条，改变这条边的颜色至无色，花费是 $w$ 。

3. $u$ 的出边中 $c$ 颜色的边有多条，改变不改变它的颜色，改变其它边的颜色至无色。
花费是 $val_{u, c} - w$ 。 $val_{u, c}$ 代表所有 $u$ 的出边中颜色是 $c$ 的边的代价之和。

不难发现，情况 $1$ 可以归到情况 $3$ 中。

我们考虑把这两种代价看做两种边权跑最短路会有什么问题：

如果按照情况 $3$ 从 $u$ 到 $v$ ，我们考虑会不会存在一个问题：按照情况 $3$ 我们需要把其它颜色也为 $c$ 的边都改成无色，那么把它变成无色但是却不记录会不会影响后面答案的计算呢？

蓝色点表示最优路径的点，红色的边表示情况 $3$ 中染成无色的边，它们的颜色是 $c$ 。黑色的边表示最优路径的边。那么如果出现上图的情况(从 $5$ 号点走到 $1$ 号点)，那么 $2$ 号点到 $1$ 号点似乎是不需要花费的，因为在从 $4$ 号点到 $3$ 号点的时候就把那条颜色为 $c$ 的边染成了无色。但是我们按照上面的规则进行的话，如果从 $2$ 到 $3$ 还使用情况 $3$ ，显然会多算一个代价。

但是深入思考一下，这种情况不会发生。因为这样的路径一定不是最优路径。如果按照上图的走法，那么 $(2, 4)$ ， $(6, 4)$ ， $(4, 7)$ 的代价都会被算。实际上如果我们直接选择路径 $\to 4 \to 2 \to 1$ ，并且 $(4, 2)$ 使用情况 $2$ ， $(2, 1)$ 使用情况 $3$ 肯定更加优秀。

这也就意味着： 如果我们能够通过某种方式处理好情况 $2$ 带来的影响（即把边染成无色的影响），那么按照上面的规则跑最短路就是对的。

如果按照情况 $2$ 经过一条颜色为 $c$ 的边从 $u$ 到 $v$ ，那么 $(u, v)$ 这条边颜色的改变可能会影响从 $v$ 到 $k$ 经过一条颜色为 $c$ 按照情况 $3$ 所花费的代价。根据这个问题，我们考虑拆点。

有一个很暴力的想法是我们把每一个点拆成 $m + 1$ 个点：若有三个点 $a$ , $b$ , $c$ 。 $a$ 到 $b$ 经过一条颜色为 $x$ 的边，当使用情况 $2$ 的时候，可以从 $a$ 走向 $b_x$ ，代价为 $0$ ， $b_x$ 必须继续沿着颜色x使用情况 $3$ 走向其他点。每一个点的 $0$ 状态表示 没有限制。这样我们就解决了维护信息的问题。但是复杂度好像有点问题。

我们考虑实际上一个点没有必要开 $m$ 个点，只需要对每个点开其存在的颜色数个点就行了。一条边能够提供给两个点分别提供 $1$ 个点，所以总点数是 $2 m + n$ 。然后建图跑最短路即可。时间复杂度 $O((n + m)log_2(n + m))$ 。常数有亿点大。

CODE：

#include<bits/stdc++.h>//拆点   把点的状态拆一下 
using namespace std;
const int N = 1e5 + 10;
const int M = 2e5 + 10;
const int T = 2 * N + M * 2;
typedef pair< int, int > PII;
typedef long long LL;
inline int read(){int x = 0, f = 1; char c = getchar();while(!isdigit(c)){if(c == '-') f = -1; c = getchar();}while(isdigit(c)){x = (x << 1) + (x << 3) + (c ^ 48); c = getchar();}return x * f;
}
int u, v, c;
int n, m, head[T], ut[M], vt[M], ct[M], tot, len;//最多T个点
bool vis[T];
LL wt[M], dis[T], res, w; 
map< PII, int > rk;
map< PII, LL > val;
struct edge{int v, last;LL w;
}E[M * 8 + 10000];
void add(int u, int v, LL w){E[++len].v = v;E[len].last = head[u];E[len].w = w;head[u] = len;
}
struct state{int x; LL w;friend bool operator < (state a, state b){return a.w > b.w;}
};
void dijkstra(int s){priority_queue< state > q;q.push((state){s, 0});while(!q.empty()){state u = q.top(); q.pop();int x = u.x;if(vis[x]) continue;vis[x] = 1;for(int i = head[x]; i; i = E[i].last){int v = E[i].v; LL w = E[i].w;if(dis[v] > dis[x] + w){dis[v] = dis[x] + w;q.push((state){v, dis[v]});}}}
}
int main(){n = read(), m = read();for(int i = 1; i <= n; i++){rk[make_pair(i, 0)] = ++tot;}for(int i = 1; i <= m; i++){u = read(), v = read(); c = read(), w = 1LL * read();if(!rk[make_pair(u, c)]) rk[make_pair(u, c)] = ++tot;if(!rk[make_pair(v, c)]) rk[make_pair(v, c)] = ++tot;val[make_pair(u, c)] += w;val[make_pair(v, c)] += w;ut[i] = u, vt[i] = v, wt[i] = w, ct[i] = c;}for(int i = 1; i <= m; i++){int u = ut[i], v = vt[i], c = ct[i], w = wt[i];add(rk[make_pair(u, 0)], rk[make_pair(v, 0)], w);//改变颜色，不做限制 add(rk[make_pair(u, 0)], rk[make_pair(v, c)], 0);//改变颜色，必须限制 add(rk[make_pair(u, c)], rk[make_pair(v, 0)], val[make_pair(u, c)] - w);add(rk[make_pair(u, 0)], rk[make_pair(v, 0)], val[make_pair(u, c)] - w);add(rk[make_pair(v, 0)], rk[make_pair(u, 0)], w);//改变颜色，不做限制 add(rk[make_pair(v, 0)], rk[make_pair(u, c)], 0);//改变颜色，必须限制 add(rk[make_pair(v, c)], rk[make_pair(u, 0)], val[make_pair(v, c)] - w);add(rk[make_pair(v, 0)], rk[make_pair(u, 0)], val[make_pair(v, c)] - w);}memset(dis, 0x3f, sizeof dis);dis[rk[make_pair(1, 0)]] = 0;dijkstra(rk[make_pair(1, 0)]);res = dis[rk[make_pair(n, 0)]];if(res == 0x3f3f3f3f3f3f3f3f) res = -1;printf("%lld\n", res);return 0;
}