分层图最短路

按P4568 [JLOI2011]飞行路线这个题来说。

主要思路

走每条边时可以有\(K\)次让这条边免费的机会。

建图的方法是，原图先建好，针对\(K\)次免费的机会，每次机会新建一层图，新建的每层图与原图相同，

这里层就理解为上下排列着的，然后对于原图中的\(u→v\)的边，在每相邻两层图之间连一条\(u→v\)的边，

层间的边边权为\(0\)，例如下图\(K=1\)，为了简洁画的有向图。

蓝色边就是层间的边，例如原图中有边权为\(0\)的边，在分层图中就从原图中的\(1\)向下一层的\(2\)建边，边权为0。

这样跑最短路时每垮一层图就表示用掉了一次免费的机会。

这样连边会多连出很多边，所以注意计算加边数组的大小，而且每层图会多开点，还要注意计算点集大小。

这个题边集是\(50000\)的，\(K\)最多是\(10\)，原图加两条边，其它层的图及层之间会加\(4\)条边，

每次最多加\(42\)条边，所以边集要开到\((4∗10+2)∗50000=2100000\)

每层图要多开\(n\)个点，所以点集是\(10000+10000∗10=110000\)的，注意都\(+10\)

code

#include <bits/stdc++.h>

#define N 110010
#define M 2100010
#define ll long long

using namespace std;
const int inf = 2147483647;
int n, m, k, s, t; bool vis[N];
int head[N], add_edge, dis[N];
struct qaq {
	int next, to, dis;
}edge[M];
struct node {
	int point, dist;
	bool operator < (const node &b) const {
		return dist > b.dist;
	}
}; 

int read() {
	int s = 0, f = 0; char ch = getchar();
	while (!isdigit(ch)) f |= (ch == '-'), ch = getchar();
	while (isdigit(ch)) s = s * 10 + (ch ^ 48), ch = getchar();
	return f ? -s : s;
}

void add(int from, int to, int dis) {
	edge[++add_edge].next = head[from];
	edge[add_edge].dis = dis;
	edge[add_edge].to = to;
	head[from] = add_edge;
}

void dijkstra(int s) {
	memset(dis, 127, sizeof dis);
	dis[s] = 0;
	priority_queue<node> q;
	q.push((node){s, 0});
	while (!q.empty()) {
		node fr = q.top(); q.pop();
		int x = fr.point;
		if (vis[x]) continue;
		vis[x] = 1;
		for (int i = head[x]; i; i = edge[i].next) {
			int to = edge[i].to;
			if (!vis[to] && dis[to] > dis[x] + edge[i].dis) {
				dis[to] = dis[x] + edge[i].dis;
				q.push((node){to, dis[to]});
			}
		} 
	}
}

void add_work() {
	s = read(), t = read();
	for (int i = 1, a, b, d; i <= m; i++) {
		a = read(), b = read(), d = read();
		add(a, b, d), add(b, a, d);
		for (int j = 1; j <= k; j++) {
			add(a + (j - 1) * n, b + j * n, 0);
			add(b + (j - 1) * n, a + j * n, 0);
			add(a + j * n, b + j * n, d);
			add(b + j * n, a + j * n, d);
		}
	}
	
	dijkstra(s);
}

int main() {
	n = read(), m = read(), k = read();
	add_work();
	int ans = inf;
	for (int i = t; i <= n * (k + 1); i += n)
		ans = min(ans, dis[i]);
	cout << ans;
}            		
           

几个练习题

P2939 [USACO09FEB]Revamping Trails G

https://www.luogu.com.cn/problem/P4822