考虑维护按照边权最小的堆，维护结点信息如下:
代码语言：javascript复制int u; // 上一个结点
int v; // 当前结点
LL lst; // 到上一个结点u的距离
LL now; // 到当前结点v的距离
int id; // 上一个结点u下一次需要扩展的下标一开始，先将每个结点从最短的那条边扩展，然后对于每次操作。取队头元素，当前的路径距离就是第$idx$小的路径，用队头元素进行扩展:
- 从结点$v$最短的一条边扩展
- 从结点u的$id$下标编号进行扩展
扩展的时候维护上述信息。
这种贪心策略就是很对。
代码语言：javascript复制#include <bits/stdc .h>
using namespace std;
typedef long long LL;
#define dbg(x) cout << #x"=" << x << endl;
#define SZ(x) (int)(x).size()
struct Node{
int u; // 上一个结点
int v; // 当前结点
LL lst; // 到上一个结点u的距离
LL now; // 到当前结点v的距离
int id; // 上一个结点u下一次需要扩展的下标
bool operator<(const Node &b)const{
return now > b.now;
}
void pt(){
dbg(u)
dbg(v)
dbg(lst)
dbg(now)
dbg(id)
dbg("----")
}
};
typedef pair<LL, int> P;
#define w_ first
#define v_ second
const int MAX_M = 5*1e4 100;
int Q[MAX_M], A[MAX_M];
int n,m,q;
vector<P> G[MAX_M];
void solve(){
cin >> n >> m >> q;
for(int i = 1; i <= n; i) G[i].clear();
int u,v;
LL w;
priority_queue<Node> que;
for(int i = 1; i <= m; i){
cin >> u >> v >> w;
G[u].push_back(make_pair(w, v));
}
int mxK = 0;
for(int i = 1; i <= q; i){
cin >> Q[i];
mxK = max(mxK, Q[i]);
}
for(int i = 1; i <= n; i){
sort(G[i].begin(), G[i].end());
if(SZ(G[i])){ // 从G[i]最小的扩展出一条边
P e = G[i][0];
que.push((Node){i, e.v_, 0, e.w_, 1});
}
}
int idx = 0;
/*
int u; // 上一个结点
int v; // 当前结点
LL lst; // 到上一个结点u的距离
LL now; // 当当前结点v的距离
int id; // 上一个结点u需要扩展的下标
*/
while(idx < mxK){
Node p = que.top();
que.pop();
A[ idx] = p.now;
// 从v扩展当前结点最小的边
if(SZ(G[p.v])) {
P e = G[p.v][0];
que.push((Node){p.v, e.v_, p.now, p.now e.w_, 1});
}
// 通过G[p.u][p.id]扩展
if(p.id < SZ(G[p.u])){
P e = G[p.u][p.id];
que.push((Node){p.u, e.v_, p.lst, p.lst e.w_, p.id 1});
}
}
for(int i = 1; i <= q; i){
cout << A[Q[i]] << endl;
}
}
int main(){
//freopen("in.txt", "r", stdin);
ios::sync_with_stdio(0); cin.tie(0);
int T;
cin >> T;
while(T--) solve();
return 0;
}
