分层图
dist[i][j]
表示到i
点经过j
条0
权边
新图dist[n][k]
有k+1
层,分别为dist[n][0],dist[n][1]....dist[n][k]
,每层图有0,1,2...k
条0
权边,每层图通过加一条0
权边进入下一层,也就是dist[n][0]
能进入dist[n][1]
,dist[n][1]
能进入dist[n][2]
,反过来不行
因为没有负权边,最终在这张大图上dijkstra
求最短路,最短路的值保存当前路线上最大值
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 1010, M = 20010, INF = 0x3f3f3f3f;
int n, m, k;
int d[N][N];
bool st[N][N];
int h[N], e[M], ne[M], w[M], idx;
void add(int a, int b, int c)
{
e[++ idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx;
}
void dijkstra()
{
memset(d, 0x3f, sizeof d);
d[1][0] = 0;
priority_queue<pair<int, PII>> heap;
heap.push({0, {1, 0}}); // {当前路上花费 d[i][j],{点 i,第几层图 j}}
while (heap.size())
{
auto t = heap.top();
heap.pop();
int i = t.y.x, j = t.y.y;
if (st[i][j]) continue;
st[i][j] = true;
for (int u = h[i]; u; u = ne[u])
{
int next = e[u], weight = w[u]; // 每个点只有两种操作
if (d[next][j] > max(d[i][j], weight)) // 在当前层不变,去下一个点
{
d[next][j] = max(d[i][j], weight);
heap.push({-d[next][j], {next, j}}); // 默认大根堆,加负号变小根堆
}
if (j < k && d[next][j + 1] > d[i][j]) // 去下一层图的下一个点
{
d[next][j + 1] = d[i][j];
heap.push({-d[next][j + 1], {next, j + 1}});
}
}
}
}
int main()
{
scanf("%d%d%d", &n, &m, &k);
for (int i = 0; i < m; i ++)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
add(b, a, c);
}
dijkstra();
int res = INF;
for (int i = 0; i <= k; i ++) res = min(res, d[n][i]); // 结果取每个图中到n点最小值
if (res == INF) puts("-1");
else printf("%d\n", res);
return 0;
}
二分
题意:找所有1
到n
的路径中第k+1
大的边之中最小的那个
在0
到1e6
(最大边权)之间,每个值代表边长,边长关于到终点的路径中他最小是第几大的边不严格单调(它关于最少要经过多少条大于自己的边到终点不严格单调)
对于j
,从1
到n
最少经过k
条大于自己的边到终点,对于小于j
的边,最少经过k
条大于自己的边到终点,因为所有路径至少k
条大于j
的边,不严格单调递增
定义一个算法:求j
最少经过多少条比它大的边到终点n
用j
表示边大小,大于j
的边权记1
,小于等于的记0
,求1
到n
的最短路,最短路值记作num
,表示从1
到n
最少经过m
条大于j
的边,j
最小就是m+1
大的边(如果j
存在)
能够改变排名的边一定是真实的边
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
using namespace std;
const int N = 1010, M = 20010;
int n, m, k;
int d[N];
bool st[N];
int h[N], e[M], ne[M], w[M], idx;
void add(int a, int b, int c)
{
e[++ idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx;
}
bool check(int x)
{
memset(d, 0x3f, sizeof d);
memset(st, 0, sizeof st);
d[1] = 0;
deque<int> q;
q.push_back(1);
while (q.size())
{
auto t = q.front();
q.pop_front();
if (st[t]) continue;
st[t] = true;
for (int i = h[t]; i; i = ne[i])
{
int j = e[i], z = w[i] > x;
if (d[j] > d[t] + z)
{
d[j] = d[t] + z;
if (z == 0) q.push_front(j);
else q.push_back(j);
}
}
}
return d[n] <= k;
}
int main()
{
scanf("%d%d%d", &n, &m, &k);
for (int i = 0; i < m; i ++)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
add(b, a, c);
}
int l = 0, r = 1e6 + 1;
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid; // 小于等于k条,边可能大了,我们要找到极限值那条真实存在的边
else l = mid + 1; // r再小一点d[n]就大于k了,这个点就是最小的
}
if (l == 1e6 + 1) puts("-1"); // 1到不了n,d[n]=0x3f3f3f3f,每次执行l=mid+1
else printf("%d\n", l);
return 0;
}