# hdu path 6705 最短路

题意  输出所有路径的第k短路

```#include<bits/stdc++.h>
#define pi pair<int, int>
#define mk make_pair
#define ll long long
using namespace std;
const int maxn = 5e4 + 10;
struct node {
int u;
ll dis;
bool operator<(const node& t) const {
return dis > t.dis;
}
};
vector<pi> G[maxn];
priority_queue<node> q;
multiset<ll> s;
ll ans[maxn * 10];
int  qry[maxn];
void init(int n) {
s.clear();
for (int i = 1; i <= n; i++)
G[i].clear();
while (!q.empty())
q.pop();
}
int main()
{
int T;
scanf("%d", &T);
while (T--) {
int n, m, Q, u, v, w, k, mx = 0;
scanf("%d%d%d", &n, &m, &Q);
for (int i = 1; i <= m; i++) {
scanf("%d%d%d", &u, &v, &w);
G[u].push_back(mk(w, v));
q.push(node{v, w});
s.insert(w);
}
for (int i = 1; i <= n; i++)
sort(G[i].begin(), G[i].end());
for (int i = 1; i <= Q; i++)
scanf("%d", &qry[i]), mx = max(mx, qry[i]);
int cnt = 0;
while (cnt < mx) {
node tmp = q.top();
q.pop();
ans[++cnt] = tmp.dis;
if (cnt >= mx)
break;
u = tmp.u;
for (auto it : G[u]) {
v = it.second;
ll w = it.first + tmp.dis;
if (s.size() == mx) {
auto cat = --s.end();
if (w >= *cat)
break;
s.erase(cat);
s.insert(w);
}
else
s.insert(w);
q.push(node{v, w});
}
}
for (int i = 1; i <= Q; i++)
printf("%lld\n", ans[qry[i]]);
init(n);
}
}```
View Code