洛谷P4568 [JLOI2011]飛行路線 (分層圖最短路)

原題連接配接

題意

在m條航線中，可以選擇k條路線免費，問從st到ed的最小花費是多少。

觀察一下題目資料，n隻有2e4而k隻有10，是以n*（k+1）個點的時間複雜度也綽綽有餘，這時就可以利用分層圖的思想來寫。

解題思路

将整個圖想象成一個三維的立體空間，那麼1到n個點排在第一層，n+1到2n的點排在第2層……依次類推，那麼我們可以假設層與層之間的聯系為免費的路線，每上一層相當于利用一次免費的機會，層之間當然是隻上不下，是以如果有k次免費機會，那麼就會有k+1層的圖，最後答案肯定在每一層的st中找。

#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
const int M = 2000010;
int ne[2 * M], vi[2 * M], e[2 * M], h[N];
int tot, n, m, k, st, ed;
int dis[N], vis[N];

void add(int u, int v, int w) {
	e[tot] = v, vi[tot] = w, ne[tot] = h[u], h[u] = tot++;
}

struct node {
	int d, now;
	bool operator < (const node& x) const {
		return d > x.d;
	}
};

priority_queue<node> q;
void dijkstra(int s) {
	memset(dis, 0x3f, sizeof dis);
	dis[s] = 0;
	q.push(node{ dis[st], st });
	while (q.size()) {
		node p = q.top();
		q.pop();
		int u = p.now;
		if (vis[u]) continue;
		vis[u] = 1;
		for (int i = h[u]; ~i; i = ne[i]) {
			int v = e[i];
			if (dis[v] > dis[u] + vi[i]) {
				dis[v] = dis[u] + vi[i];
				if (!vis[v]) {
					q.push(node{ dis[v], v });
				}
			}
		}
	}
}

int main() {
	cin >> n >> m >> k;
	cin >> st >> ed;
	st++, ed++;
	memset(h, -1, sizeof h);
	for (int i = 0; i < m; i++) {
		int x, y, z;
		cin >> x >> y >> z;
		x++, y++;
		add(x, y, z), add(y, x, z);
		for (int j = 1; j <= k; j++) {
			add(x + j * n, y + j * n, z);
			add(y + j * n, x + j * n, z);
			add(x + (j - 1) * n, y + j * n, 0);
			add(y + (j - 1) * n, x + j * n, 0);
		}
	}
	
	dijkstra(st);
	int res = 999999999;
	for (int i = ed; i <= (k + 1) * n; i += n) res = min(res, dis[i]);
	cout << res << endl;
}