分層圖最短路

按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