方法一:分层图最短路
设 $f_{x,k}$ 表示到达 $x$ 后,从经过的路径中选取最贵的 $k$ 条免费,最小的总花费。
对于一条边 x->y
,长度为 z
,有 $f_{y,k}=\min\(f_{y,k}, \max\(f_{x,k}, z\)\)$ , $f_{y,k+1}=\min\(f_{y,k + 1}, f_{x,k}\)$
显然这个dp有后效性,但是我们可以考虑建立 $N*K$ 个节点,分别表示状态 $(x, k)$ ,原来的dp可以看做一个最短路问题。
具体来说,将节点按照 $k$ 分层,同一层之间节点若有边连接,则边权为 $z$ ,同时将计算最短路的直接相加转化为 $\max$ 。对于不同层的节点,对应的 $(x,k)$ 向 $(y, k + 1)$ 连一条长度为 $0$ 的边。复杂度为 $O(tNP)$ 。
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
using namespace std;
typedef pair<int, int> PII;
const int N = 1005, K = 1005, INF = 0x7f7f7f7f;
int n, m, k, d[N][K]; bool v[N][K];
vector<pair<PII, int> > g[N][K];
void spfa()
{
queue<PII> q; q.push({1, 0});
d[1][0] = 0; v[1][0] = 1;
while(q.size())
{
int x = q.front().first, p = q.front().second; q.pop();
v[x][p] = 0;
for(int i = 0; i < g[x][p].size(); i ++ )
{
int y = g[x][p][i].first.first, t = g[x][p][i].first.second;
int z = g[x][p][i].second;
if(d[y][t] > max(d[x][p], z))
{
d[y][t] = max(d[x][p], z);
if(!v[y][t]) q.push({y, t}), v[y][t] = 1;
}
}
}
}
int main()
{
scanf("%d%d%d", &n, &m, &k);
memset(d, 0x7f, sizeof d);
for(int i = 1; i <= m; i ++ )
{
int x, y, z; scanf("%d%d%d", &x, &y, &z);
for(int j = 0; j <= k; j ++ )
{
g[x][j].push_back({{y, j}, z});
g[x][j].push_back({{y, j + 1}, 0});
g[y][j].push_back({{x, j}, z});
g[y][j].push_back({{x, j + 1}, 0});
}
}
spfa();
printf("%d\n", (d[n][min(m, k)] == INF ? -1 : d[n][min(m,k)]));
return 0;
}
方法二:二分答案+ $0/1$ 最短路
显然答案具有单调性,故二分答案,对于二分到的答案 $mid$ ,把边权 $\le mid$ 的边权改为 $0$ , $>mid$ 的改为 $1$ ,求 $1$ 到 $n$ 的最短路,检查是否 $\le k$ ,若是则 $r=mid$ ,否则 $l = mid + 1$ ,复杂度 $O((N+P)\log L)$
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<list>
using namespace std;
const int N = 1e3 + 10, M = 1e4 + 10;
int n, m, k, head[N], Next[M << 1], ver[M << 1], edge[M << 1], tot;
bool v[N]; int d[N];
void add_edge(int x, int y, int z)
{
ver[++tot] = y; edge[tot] = z;
Next[tot] = head[x]; head[x] = tot;
}
int bfs(int mid)
{
memset(d, 0x7f, sizeof d);
memset(v, 0, sizeof v);
list<int> q; q.push_back(1); d[1] = 0;
while(q.size())
{
int x = *q.begin(); q.pop_front(); v[x] = 1;
for(int i = head[x]; i; i = Next[i])
{
int y = ver[i], z = (edge[i] > mid);
if(v[y]) continue;
if(d[y] > d[x] + z)
{
d[y] = d[x] + z;
z ? q.push_back(y) : q.push_front(y);
}
}
}
return d[n] <= k;
}
int main()
{
scanf("%d%d%d", &n, &m, &k);
int l = 0, r = 0;
for(int i = 1; i <= m; i ++ )
{
int x, y, z; scanf("%d%d%d", &x, &y, &z);
add_edge(x, y, z); add_edge(y, x, z); r = max(r, z);
}
int Mx = ++ r;
while(l < r)
{
int mid = l + r >> 1;
if(bfs(mid)) r = mid;
else l = mid + 1;
}
printf("%d\n", l == Mx ? -1 : l);
return 0;
}