path hdu6705

题意：

一个有向加权图，问所有路径汇中第k小的路径长度是多少？
注意一个边可以反复走多次

题解

做法参考
我们可以利用优先队列来做
利用优先队列实现每次所取为最短边
我们假设一条路是从u—>v,路径和为sum，u->v是u的所以出边中边权第cur小的边，那么我们接下来有两种方案可以走：
第一种：就是接着从v走下去，从v继续走到v->w,(w为距离v最近的点，w！=u)，cur为0，因为w是v第(cur+1)小的选择，也就是g[v][0]=w
此时sum+g[v][0]
第二种：
我认为这一步算是返回的步骤
就是继续从u出发，走u下一个边权较大于v的点，因为v是第cur小的选项，所以此等方案为cur+1
sum-g[u][cur].w+g[u][cur+1].w
我们的sum是记录了u到v的边权，所以先去掉，再加上新边权

代码中的cur是用来距离v是u的第几小的选择，
我们全程不断计算新的路径情况，并将路径长度存到优先队列q中，不断排序

代码

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=5e5+50;
int n,m,q;
LL ans[maxn];
struct edge
{
   
    int to;
    LL w;
};
vector<edge> g[maxn];
bool cmp(const edge &x,const edge &y)
{
   
    return x.w<y.w;
}
struct node
{
   
    int u,v;
    int cur;
    LL sum;
    friend bool operator < (const node &x,const node &y)
    {
   
        return x.sum>y.sum;
    }
};
void init()
{
   
    for(int i=1;i<=n;i++)
        g[i].clear();
}
void solve()
{
   
    for(int i=1;i<=n;i++)
        sort(g[i].begin(),g[i].end(),cmp);
    priority_queue<node> q;
    for(int i=1;i<=n;i++)
    {
   
        if(!g[i].empty())
            q.push(node{
   i,g[i][0].to,0,g[i][0].w});
    }
    for(int i=1;i<=50000;i++)
    {
   
        int u=q.top().u,v=q.top().v,cur=q.top().cur;
        LL sum=q.top().sum;
        q.pop();
        ans[i]=sum;
        if(!g[v].empty())
            q.push(node{
   v,g[v][0].to,0,sum+g[v][0].w});
        if(cur+1<g[u].size())
            q.push(node{
   u,g[u][cur+1].to,cur+1,sum-g[u][cur].w+g[u][cur+1].w});
    }
}
int main()
{
   
    int T;
    scanf("%d",&T);
    while(T--)
    {
   
        scanf("%d %d %d",&n,&m,&q);
        init();
        for(int i=1;i<=m;i++)
        {
   
            int u,v,w;
            scanf("%d %d %d",&u,&v,&w);
            g[u].push_back(edge{
   v,w});
        }
        solve();
        while(q--)
        {
   
            int k;
            scanf("%d",&k);
            printf("%lld\n",ans[k]);
        }
    }
    return 0;
}