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<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;
}