http://acm.hdu.edu.cn/showproblem.php?pid=6705
这是比赛前8题过的人数第二少的题，于是就来补了，但感觉并不难啊。。（怕不是签到难度
题意：给个图，给几条路，让你求第k短路，所有路径不限制使用次数。
思路：最短路肯定是最短的那条，第2短就有2种可能，可能是长度第二短的那条，也有可能是接着刚才的最短路继续走（2个还不会，但是先这样拓展），到第3短就真的是2种可能了（例如1，2，9，1+2<9），但是k短路显然最多是由k段拼成（反证法：如果是k+1条，那个把第k+1段扔了就会更小，所以肯定不是最优），所以直接循环max(k)次，第i次循环就把i段拼成的路更新进去就行。可以开优先队列，装路径总长和终点的struct。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e4+10;
struct node{
ll to,len;
node(){}
node(ll a,ll b):to(a),len(b){}
};
struct cmp{
bool operator ()(const node &x,const node &y) const{
return x.len>y.len;
}
};
bool cmp1(node a,node b){
return a.len<b.len;
}
priority_queue<node,vector<node>,cmp > q0;
priority_queue<int> q1;
vector<node> ve[N];
ll a[N],b[N];
void init(int n){
while(!q1.empty()) q1.pop();
while(!q0.empty()) q0.pop();
for(int i=1;i<=n;i++) ve[i].clear();
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll t;
cin>>t;
while(t--){
ll n,m,k;
cin>>n>>m>>k;
init(n);
for(ll i=1;i<=m;i++){
ll u,v,w;
cin>>u>>v>>w;
q0.push({v,w});
q1.push(w);
ve[u].push_back(node(v,w));
}
for(ll i=1;i<=n;i++){
sort(ve[i].begin(),ve[i].end(),cmp1);
}
ll mx = 0;
for(ll i=0;i<k;i++){
cin>>a[i];
mx = max(mx,a[i]);
}
for(ll i=1;i<=mx;i++){
b[i] = q0.top().len;
ll x = q0.top().to;
q0.pop();
for(int j=0;j<ve[x].size();j++){
ll y=ve[x][j].to,len=b[i]+ve[x][j].len;
if(q1.size()==mx){
if(len>q1.top()) break;
else{
q1.pop();
q1.push(len);
q0.push({y,len});
}
}
else {
q1.push(len);
q0.push({y,len});
}
}
}
for(ll i=0;i<k;i++) cout<<b[a[i]]<<endl;
}
return 0;
}
原文：https://www.cnblogs.com/wzgg/p/11410161.html