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$ 颜色的边有多条，改变不改变它的颜色，改变其它边的颜色至无色。
            花费是 $va{l}_{u,c}-w$。 $va{l}_{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)$ 的代价都会被算。实际上如果我们直接选择路径 $5\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$ 个点，所以总点数是 $2m+n$。然后建图跑最短路即可。时间复杂度 $O((n+m)lo{g}_2(n+m))$。常数有亿点大。

CODE：

#include//拆点   把点的状态拆一下 
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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85