洛谷:飞行路线
跟Acwing的 通信线路 一样,数据小一点,也是可以二分做的(具有单调性质)
只有部分一致,一个求最小路径花费、一个求路径上最大的边权的最小值
对路径上最大边权二分答案,不能保证路径花费(所有小于最大边权的边加起来)就最小
所以此题二分是错解(x)
分层图做法:
根据 k 次免费,建 k 层图,上一层走到下一层相当于免费做了次航班
跟dp的状态转移很类似
记得注意下最后的 hack 数据:
有可能没使用完免费机会就达到终点,所以必须枚举减免任意次的最短路,取最小值
代码:
#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
#define mem(a,b) memset(a,b,sizeof a)
#define cinios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
#define sca scanf
#define pri printf
#define ul u << 1
#define ur u << 1 | 1
//#pragma GCC optimize(2)
//[博客地址](https://blog.csdn.net/weixin_51797626?t=1)
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 200010, M = 50010, MM = 3000010;
int INF = 0x3f3f3f3f, mod = 100003;
ll LNF = 0x3f3f3f3f3f3f3f3f;
int n, m, k, T, S, D;
int h[N], e[MM], ne[MM], w[MM], idx;
int dist[N];
bool st[N];
struct edge
{
int a, b, w;
}ed[M];
void add(int a, int b, int x) {
e[idx] = b, ne[idx] = h[a], w[idx] = x, h[a] = idx++;
}
void dj(int s) { //标准Djikstar,只是建图特别
mem(dist, 0x3f);
dist[s] = 0;
priority_queue<PII, vector<PII>, greater<PII>> q;
q.push({ 0,s });
while (q.size())
{
PII t = q.top();
q.pop();
int ver = t.second;
if (st[ver])continue;
st[ver] = true;
for (int i = h[ver]; ~i; i = ne[i]) {
int j = e[i];
if (dist[j] > dist[ver] + w[i]) {
dist[j] = dist[ver] + w[i];
q.push({ dist[j],j });
}
}
}
}
int main() {
cinios;
cin >> n >> m >> k;
cin >> S >> D;
mem(h, -1);
for (int i = 0; i < m; i++) {
int a, b, c;
cin >> a >> b >> c;
ed[i] = { a,b,c };
}
for (int i = 0; i <= k; i++) {
int step = i * n, last = (i - 1) * n;
for (int j = 0; j < m; j++) {
int a = ed[j].a, b = ed[j].b, w = ed[j].w;
add(step + a, step + b, w);
add(step + b, step + a, w);
if (i) {
add(last + a, step + b, 0);
add(last + b, step + a, 0);
}
}
}
dj(S);
//cout << dist[k * n + D];(x)
//最后可能可能没有用完 k 次机会,所以到每层终点的最短路都有可能成为答案
int mi = INF;
for (int i = 0; i <= k; i++)
mi = min(mi, dist[i * n + D]);
cout << mi;
return 0;
}
二分做法:
反转了