You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

91 lines
2.8 KiB

This file contains ambiguous Unicode characters!

This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
const int M = 1e4 + 10;
// 本题由于是有向图并且允许走回头路比如有一个环存在就可以重复走直到第K次到达即可这与传统的最短路不同,所以没有st数组存在判重
int n, m; // n个顶点,m条边
int S, T; // 起点与终点
int K; // 第K短的路线
int cnt[N]; // 记录某个点出队列的次数
int h[N], w[M], e[M], ne[M], idx; // 邻接表
int dist[N]; // 到每个点的最短距离
void add(int a, int b, int c) {
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
struct N1 {
int u, d;
const bool operator<(const N1 &b) const {
return d > b.d; // 谁的距离短谁靠前
}
};
// 堆优化版本Dijkstra
void dijkstra() {
// 小顶堆
priority_queue<N1> q;
// 起点入队列
q.push({S, 0});
while (q.size()) { // bfs搜索
int d = q.top().d; // 当前点和出发点的距离
int u = q.top().u; // 当前点u
q.pop();
cnt[u]++; // 记录u节点出队列次数
if (u == T && cnt[u] == K) { // 如果到达了目标点+第K次到达
printf("%d", d); // 输出距离长度
return;
}
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
/*
对比标准版本 Dijkstra
if (!st[u]) {
st[u] = 1;
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
if (d[v] > dist + w[i]) {
d[v] = dist + w[i];
q.push({d[v], v});
}
}
}
① 取消了st[u]:因为一个点可以入队列多次
② 不是最短的才可以入队列,是谁都可以
*/
if (cnt[v] < K)
q.push({v, d + w[i]}); // 不管长的短的全部怼进小顶堆不是最短路径才是正解是所有路径都有可能成为正解所以这里与传统的Dijkstra明显不一样
}
}
puts("-1");
}
// 通过了 6/7个数据
// 有一个点TLE看来暴力+Dijkstra不是正解
int main() {
// 初始化邻接表
memset(h, -1, sizeof h);
// 寻找第K短路n个顶点m条边
cin >> n >> m;
while (m--) {
int a, b, c;
cin >> a >> b >> c; // a->b有一条长度为c的有向边
add(a, b, c);
}
cin >> S >> T >> K; // 开始点结束点第K短
if (S == T) K++; // 如果S=T那么一次检查到相遇就不能算数也就是要找第K+1短路
// 迪杰斯特拉
dijkstra();
return 0;
}