HDU - 6705 path（图上不固定起点和终点的第 k 短路）

You have a directed weighted graph with nn vertexes and mm edges. The value of a path is the sum of the weight of the edges you passed. Note that you can pass any edge any times and every time you pass it you will gain the weight. 

Now there are qq queries that you need to answer. Each of the queries is about the k-th minimum value of all the paths.

Input

The input consists of multiple test cases, starting with an integer tt (1≤t≤100)(1≤t≤100), denoting the number of the test cases. 
The first line of each test case contains three positive integers n,m,q. (1≤n,m,q≤5∗104)(1≤n,m,q≤5∗104) 

Each of the next mm lines contains three integers ui,vi,wiui,vi,wi, indicating that the i−thi−th edge is from uiui to vivi and weighted wiwi.(1≤ui,vi≤n,1≤wi≤109)(1≤ui,vi≤n,1≤wi≤109) 

Each of the next qq lines contains one integer kk as mentioned above.(1≤k≤5∗104)(1≤k≤5∗104) 

It's guaranteed that ΣnΣn ,ΣmΣm, Σq,Σmax(k)≤2.5∗105Σq,Σmax(k)≤2.5∗105 and max(k)max(k) won't exceed the number of paths in the graph. 

Output

For each query, print one integer indicates the answer in line.

Sample Input

1
2 2 2
1 2 1
2 1 2
3
4

Sample Output

3
3

        
  

Hint

1->2 value :1

2->1 value: 2

1-> 2-> 1 value: 3

2-> 1-> 2 value: 3

题意：给出一个图，和若干次询问，每次询问回答图上不固定起点和终点的第 k 短路。

思路：先把每个点对应的最短边扔进优先队列，按路径长度从小到大取出，从这条边上扩展最小的出边，这样第 i 次取出的边就是第 i 短的。

思路转自https://www.cnblogs.com/kangkang-/p/11405979.html

#include<bits/stdc++.h>
using namespace std;
const int eps = 1e-8;
const int N = 5e4 + 10;

vector<pair<int, int> >mp[N];

struct node {
    int w, u, id;
    node(){}
    node(int uu, int idd, int ww) : u(uu), id(idd), w(ww){}
    bool operator < (const node &a)const {
        return w > a.w;
    }
};

int ans[N], qq[N];

int main() {
    int t, n, m, u, v, w, Q;
    scanf("%d", &t);
    while(t--) {
        scanf("%d%d%d", &n, &m, &Q);
        for(int i = 1; i <= n; ++i) mp[i].clear();
        for(int i = 1; i <= m; ++i) {
            scanf("%d%d%d", &u, &v, &w);
            mp[u].push_back(make_pair(w, v));
        }
        for(int i = 1; i <= n; ++i) {
            sort(mp[i].begin(), mp[i].end());
        }
        int maxx = 0;
        for(int i = 0; i < Q; ++i) {
            scanf("%d", &qq[i]);
            maxx = max(maxx, qq[i]);
        }
        priority_queue<node>q;
        for(int i = 1; i <= n; ++i) {
            if(mp[i].size())
                q.push(node(i, 0, mp[i][0].first));
        }
        int cnt = 0;
        while(!q.empty()) {
            node tmp = q.top();
            q.pop();
            int u = tmp.u, id = tmp.id, w = tmp.w;
            ans[++cnt] = w;
            if(cnt == maxx) break;
            if(id < (int)mp[u].size() - 1) {
                q.push(node(u, id + 1, w - mp[u][id].first + mp[u][id + 1].first));
            }
            int v = mp[u][id].second;
            if(mp[v].size())
                q.push(node(v, 0, w + mp[v][0].first));
        }
        for(int i = 0; i < Q; ++i) printf("%d\n", ans[qq[i]]);
    }
    return 0;
}