题意：
给出n个点，m条有向边的图，Q次询问，每次询问第K短路的路径长度

---

题解：
由于起点和终点都不固定，所以A*肯定是不行的了

首先先把每个点所连的点按照边权排序

考虑对于已知的最小边，需要如何拓展，假设当前边的起点是u，终点是v，我们每次拓展的时候，就只需要拓展到u的下一条边或者v点的最小边，因为我们是排过序的，所以这样拓展一定是最优的，然后用优先队列记录一下路径和即可

---

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#include<ext/rope>
using namespace std;
using namespace __gnu_cxx;
#define int long long
const int MAXN = 5e4+50;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
vector<pair<int,int> > g[MAXN];
int n,m,mx,Q,q[MAXN],res[MAXN];
struct node{int w,st,id;bool operator < (const node &x) const{ return w>x.w; }
};
inline void BFS(){priority_queue<node> que;for(int i=1;i<=n;i++) if(g[i].size()) que.push({g[i][0].first,i,0});int tot=0;while(true){node u = que.top(); que.pop();int w=u.w,st=u.st,id=u.id;res[++tot]=w;if(tot==mx) return;if(id+1<(int)g[st].size()) que.push({w-g[st][id].first+g[st][id+1].first,st,id+1});int x=g[st][id].second;if(g[x].size()) que.push({w+g[x][0].first,x,0});}
}
signed main(){
#ifndef ONLINE_JUDGEfreopen("C:\\Users\\Administrator\\Desktop\\in.txt","r",stdin);
#endif // ONLINE_JUDGEios::sync_with_stdio(false); cin.tie(0); cout.tie(0);int T; cin>>T;while(T--){cin>>n>>m>>Q; mx=0;for(int i=1;i<=n;i++) g[i].clear();for(int i=1;i<=m;i++){int u,v,w; cin>>u>>v>>w;g[u].push_back(make_pair(w,v));}for(int i=1;i<=n;i++) sort(g[i].begin(),g[i].end());for(int i=1;i<=Q;i++) cin>>q[i],mx=max(mx,q[i]);BFS();for(int i=1;i<=Q;i++) cout<<res[q[i]]<<'\n';}return 0;
}