Problem
在一个无向图\(G=(V,E)\)中，可以改变\(k\)条边的权值为\(\Delta w\)，求单源最短路径。
Solution
分层图的想法就是如果有\(k\)条边权值变为\(\Delta w\)，就建\(k+1\)层图。
这个图实际上是这样的，对于每\(1\)层中相连的点对\((u,v)\)连权值为\(w\)的无向边，对于每个在原图中相连的点对\((u,v)\)由\(k\)层点\(u_k\)向\(k+1\)层点\(v_{k+1}\)以及\(k\)层点\(v_k\)向\(k+1\)层点\(u_{k+1}\)连权值为\(\Delta w\)的有向边，方向是从\(k\)层向\(k+1\)层。
这样构造完成一张分层图后，从第\(1\)层的起始点\(s_1\)求单源最短路径，最终第\(k + 1\)层的终点\(t_{k+1}\)的单源最短路径值即为答案所求。 原理其实很简单，如果从\(k\)层图到\(k+1\)层图，有向边\((u_k,v_{k+1})\)是一条\(\Delta w\)权边，走这条边，相当于把\(w\)权边变成了\(\Delta w\)权边，并且进入了\(k+1\)层。这样如果有\(k+1\)层图的话，相当于进行了\(k\)次这种操作，自然就在\(k+1\)层图求最短路中实现了\(k\)次改变边权的目标。 这是最简单的一种分层图，如果学习了更难的构图方法和题目，会再补上。题目
T1
#include#include #include #include using namespace std;const int N = 1e4 + 5, M = 5e4 + 5, K = 105;int n, m, k;struct Edge { int Next, to, dis;}e[M * K * 2];int head[N * K], num;void add(int from, int to, int dis){ e[++num].Next = head[from]; e[num].to = to; e[num].dis = dis; head[from] = num;}int dist[N * K], vis[N * K];struct node { int u, d; bool operator < (const node &x) const { return d > x.d; }};priority_queue q;void dijk(){ memset(dist, 0x3f, sizeof(dist)); dist[1] = 0; q.push((node){1, 0}); while(!q.empty()) { int u = q.top().u; q.pop(); if(vis[u]) continue; vis[u] = 1; for(int i = head[u]; i; i = e[i].Next) { int v = e[i].to, w = e[i].dis; if(dist[v] > dist[u] + w) { dist[v] = dist[u] + w; if(!vis[v]) q.push((node){v, dist[v]}); } } }}int main(){ scanf("%d%d%d", &n, &m, &k); for(int i = 1, u, v, z; i <= m; i++) { scanf("%d%d%d", &u, &v, &z); add(u, v, z); add(v, u, z); for(int j = 1; j <= k; j++) { add(j * n + u, j * n + v, z); add(j * n + v, j * n + u, z); add((j - 1) * n + u, j * n + v, 0); add((j - 1) * n + v, j * n + u, 0); } } dijk(); int ans = 0x3fffffff; for(int i = 1; i <= k + 1; i++) ans = min(dist[i * n], ans); printf("%d\n", ans); return 0;}
T2
#include#include #include #include using namespace std;const int N = 1e4 + 5, M = 5e4 + 5, K = 12;int n, m, k;int s, t;struct _edge { int Next, v, w;}e[M * K * 4 + M * 2];int head[N * K], num;void add(int from, int to, int dis){ e[++num].Next = head[from]; e[num].v = to; e[num].w = dis; head[from] = num;}int dist[N * K], vis[N * K];struct node { int u, d; bool operator < (const node &x) const { return d > x.d; }};priority_queue q;void dijk(int x){ memset(dist, 0x3f, sizeof(dist)); dist[x] = 0; q.push((node){x, 0}); while(!q.empty()) { node tp = q.top(); q.pop(); int u = tp.u; if(u == t + k * n) break; if(vis[u]) continue; vis[u] = 1; for(int i = head[u]; i; i = e[i].Next) { int v = e[i].v, w = e[i].w; if(dist[v] > dist[u] + w) { dist[v] = dist[u] + w; if(!vis[v]) q.push((node){v, dist[v]}); } } }}int main(){ scanf("%d%d%d", &n, &m, &k); scanf("%d%d", &s, &t); s++, t++; for(int i = 1, u, v, z; i <= m; i++) { scanf("%d%d%d", &u, &v, &z); u++, v++; add(u, v, z); add(v, u, z); for(int j = 1; j <= k; j++) { add(j * n + u, j * n + v, z); add(j * n + v, j * n + u, z); add((j - 1) * n + u, j * n + v, 0); add((j - 1) * n + v, j * n + u, 0); } } dijk(s); int ans = 1e9; for(int i = 0; i <= k; i++) ans = min(ans, dist[t + i * n]); printf("%d\n", ans); return 0;}
T3
#include#include #include #include using namespace std;const int N = 55, M = 1005, K = 55;int n, m, k;struct Edge { int Next, to, dis;}e[M * K * 10];int head[N * K * 10], num;void add(int from, int to, int dis){ e[++num].Next = head[from]; e[num].to = to; e[num].dis = dis; head[from] = num;}struct node { int u, d; bool operator < (const node& x) const { return d > x.d; } };priority_queue q;int dist[N * K * 10], vis[N * K * 10];void dijk(){ memset(dist, 0x3f, sizeof(dist)); dist[1] = 0; q.push((node){1, 0}); while(!q.empty()) { int u = q.top().u; q.pop(); if(vis[u]) continue; vis[u] = 1; for(int i = head[u]; i; i = e[i].Next) { int v = e[i].to, w = e[i].dis; if(dist[v] > dist[u] + w) { dist[v] = dist[u] + w; if(!vis[v]) q.push((node){v, dist[v]}); } } }}int main(){ scanf("%d%d%d", &n, &m, &k); for(int i = 1, u, v, z; i <= m; i++) { scanf("%d%d%d", &u, &v, &z); add(u, v, z); add(v, u, z); for(int j = 1; j <= k; j++) { add(j * n + u, j * n + v, z); add(j * n + v, j * n + u, z); add((j - 1) * n + u, j * n + v, z >> 1); add((j - 1) * n + v, j * n + u, z >> 1); } } dijk(); int ans = 0x7fffffff; for(int i = 1; i <= k + 1; i++) ans = min(ans, dist[i * n]); printf("%d\n", ans); return 0;}