BZOJ 2763 飞行路线

题目链接

分层图模板题
一开始写了一个 dp ，\(f[i][j]\)表示第\(i\)个点用了\(j\)次的最小值。
\(f[i][0]\)是不用免费机会，跑一次单源最短路就可以预处理。
在图上枚举转移，每次无非就是选和不选两种决策。
感觉挺对的，然而不知道怎么 WA 了...

发现这个枚举转移好像很笨，因为可以在最短路时顺便处理出来。
建立分层图\(u,j*n\)向\(v,(j+1)*n\)连边表示用一次机会到\(v\)的最小值。
\(u,j*n\)向\(v,j*n\)连边表示不使用机会。

最后把每一层的\(t\)连接起来，\(dis[t,k*n]\)即是答案

#include <bits/stdc++.h>
using namespace std;

const int N = 10005;
vector<pair<int, int> > e[N * 15];
int n, m, k, s, t, book[N * 15], dis[N * 15];

void dij(int s) {
    memset(dis, 0x3f, sizeof dis);
	dis[s] = 0;
	priority-queue<pair<int, int> > q;
	q.push({0, s});
	while (!q.empty()) {
        int now = q.top().second;
		q.pop();
		if (book[now]) continue;
		book[now] = 1;
		for (auto v : e[now]) {
			if (dis[now] + v.second < dis[v.first]) {
				dis[v.first] = dis[now] + v.second;
				q.push({-dis[v.first], v.first});
			}
		}
	}
}

int main() {
    scanf("%d %d %d %d %d", &n ,&m, &k, &s ,&t);
	for (int i = 1; i <= m; i++) {
	    int u, v, w;
		scanf("%d %d %d", &u, &v, &w);
		e[u].push-back({v, w});
		e[v].push-back({u, w});
		for (int j = 1; j <= k; j++) {
			e[u + (j - 1) * n].push-back({v + j * n, 0});
			e[v + (j - 1) * n].push-back({u + j * n, 0});
			e[u + j * n].push-back({v + j * n, w});
			e[v + j * n].push-back({u + j * n, w});
		}
	}
	for (int i = 1; i <= k; i++) e[t + (i - 1) * n].push-back({t + i * n, 0});
	dij(s);
    /*for (int i = 0; i < n; i++) 
	    for (int j = 0; j <= k; j++) {
		for (auto v : e[i]) {
            if (j != k) dp[v.first][j + 1] = min(dp[v.first][j + 1], dp[i][j]);
			if (j != 0) dp[v.first][j] = min(dp[v.first][j], dp[i][j] + v.second);
		}
	}*/
	printf("%d\n", dis[t + k * n]);
	return 0;
}