本文主要是介绍【NEERC2017 Journey from Petersburg to Moscow】【有趣的最短路变形】【取最短路上的k大和为路径长】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
链接：https://codeforces.com/gym/101630/my
题意：求1到n的最短路，最短路上只计算前k大的边。
分析：修改dijkstra模板。遍历每条边x，并把图中所有的边的权值都减去该边的权值x，如果变成负数，那么就置00，并将跑出来的值dis[n]+k∗x就是这次的答案，对所有的答案取最小值，并且与原始图的dis[n]（最短路长度小于k的情况）取最小值，得到的结果就是最终答案
证明：（摘自大佬）
1. 假设最终的最短路中有大于等于k条边，并设第k大的边长度为x。
那么该路径上所有的边减去x，之后跑最短路得到dis[n]，那么dis[n]+k∗x就是该路径的“长度”，就是最终答案，并且这个数一定会出现在比较中。 而对于其他的路径，如果减去的x不是该路径的第k大的边的时候，该路径的值dis[n]+k∗x一定不会比该路径的“长度”小，出现在比较中不会对最终答案造成影响。
2. 假设最短路中有小于k条边，那么原图中跑最短路的dis[n]一定是最小的。
注意，此题用spfa超时，用dijkstra也有稍微优化一下才行。
#pragma warning(disable:4996)
#include <bits/stdc++.h>
#include<algorithm>
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define x first
#define y second
#define rep(i,a,b) for(int i=a;i<b;++i)
#define per(i,a,b) for(int i=a-1;i>=b;--i)
#define eps 1e-8
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> VI;
typedef pair<int, int> PII;const int INF = 0x3f3f3f3f;
const ll INFLL = 0x3f3f3f3f3f3f3f3fll;typedef long long ll;
typedef pair<ll, int> pii;
const int maxn = 3e5 + 5;
const ll inf = 1e18;
int n, m;
int k;
ll dis[maxn];
vector<int>v[maxn];struct node {int u, v;ll w;
}t[maxn];ll dijkstra(ll w) {priority_queue<pii, vector<pii>, greater<pii> >q;for (int i = 1; i <= n; i++) dis[i] = inf;dis[1] = 0;q.push({ 0,1 });while (q.size()) {pii tmp = q.top(); q.pop();ll f = tmp.first;int s = tmp.second;if (f > dis[s])continue;for (int i : v[s]) {int ss = s^t[i].u^t[i].v;ll ww = t[i].w - w;ww = max(0ll, ww );if (ww + dis[s] < dis[ss]) {dis[ss] = ww + dis[s];q.push({dis[ss],ss});}}}return dis[n];
}int main() {scanf("%d%d%d", &n, &m, &k);for (int i = 1; i <= m; i++) {scanf("%d%d%lld", &t[i].u, &t[i].v, &t[i].w);v[t[i].u].push_back(i);v[t[i].v].push_back(i);}ll ans = dijkstra(0);for (int i = 1; i <= m; i++) {ll w = t[i].w;ans = min(ans, dijkstra(w)+k*w);}cout << ans << endl;
}
/*
6 7 2
1 2 6
2 3 1
2 4 3
2 5 5
3 6 10
4 6 9
5 6 85 5 3
2 1 1
3 2 1
4 3 1
4 5 1
1 5 2*/
这篇关于【NEERC2017 Journey from Petersburg to Moscow】【有趣的最短路变形】【取最短路上的k大和为路径长】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
