path -第k短路

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<queue>
 6 #include<stack>
 7 #include <bitset>
 8 #include<set>
 9 #include<map>
10 #include<unordered_map>
11 #include<vector>
12 #include<cmath>
13 typedef long long ll;
14 using namespace std;
15 typedef pair<ll, int> pa;
16 const int N = 5e4 + 1000;
17 vector<pa>ve[N];
18 const int INF = 0x3f3f3f3f;
19 int ans[N], maxk = 0, n, m, q, qq[N];
20 struct node {
21     int id, now, to;
22     ll dis;
23     //优先队列进队时，权重小的放前面
24     bool operator <(const node& a)const {
25         return dis > a.dis;
26     }
27 };
28 priority_queue<node> pr;
29 void dfs() {
30     int cnt = 0;
31     while (!pr.empty()) {
32         //选择整张图的权重最小值
33         node x = pr.top();
34         pr.pop();
35         node t;
36         ans[++cnt] = x.dis;
37         if (cnt >= maxk) {
38             break;
39         }
40         //当x点还有临边时，将x的下一个最短权重边加入队列
41         if (x.id + 1 < ve[x.now].size()) {
42             t.dis = x.dis - ve[x.now][x.id].first + ve[x.now][x.id + 1].first;
43             t.id = x.id + 1;
44             t.to = ve[x.now][x.id + 1].second;
45             t.now = x.now;
46             pr.push(t);
47         }
48         //若当前最短边的汇点有指向别的点的边，则取汇点y到别的边z的最短长度边，x，z加入队列
49         if (ve[x.to].size()) {
50             t.dis = x.dis + ve[x.to][0].first;
51             t.id = 0;
52             t.now = x.to;
53             t.to = ve[x.to][0].second;
54             pr.push(t);
55         }
56     }
57 }
58 int main() {
59     int T;
60     cin >> T;
61     while (T--) {
62         //清空优先队列和容器
63         while (!pr.empty()) {
64             pr.pop();
65         }
66         cin >> n >> m >> q;
67         for (int i = 1; i <= n; i++) {
68             ve[i].clear();
69         }
70         //将w和v放入下标为u的容器内
71         for (int i = 1; i <= m; i++) {
72             int u, v, w;
73             cin >> u >> v >> w;
74             ve[u].push_back({ w,v });
75         }
76         //将顶点内的权重排序，把顶点到临边权重最小值放入优先队列
77         for (int i = 1; i <= n; i++) {
78             if (ve[i].size()) {
79                 sort(ve[i].begin(), ve[i].end());
80                 pr.push({ 0,i,ve[i][0].second,ve[i][0].first });
81             }
82         }
83         //找出k的最大值
84         for (int i = 1; i <= q; i++) {
85             cin >> qq[i];
86             maxk = max(maxk, qq[i]);
87         }
88         dfs();
89         for (int i = 1; i <= q; i++) {
90             cout << ans[qq[i]] << endl;
91         }
92     }
93     return 0;
94 }