hdu6705 path 2019ccpc网络赛_acm.hdu6705-CSDN博客

本文链接：https://blog.csdn.net/liufengwei1/article/details/100047080

本文介绍了一种在ACM竞赛中使用的高效路径查找算法，通过定义特定的节点结构和集合操作，实现了从源点到目标点的最短路径枚举。算法利用set容器存储路径信息，通过比较路径长度和节点ID来优化路径选择，适用于解决最大路径数量限制问题。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

传送门：http://acm.hdu.edu.cn/showproblem.php?pid=6705

大概是这题的加强版，https://blog.csdn.net/liufengwei1/article/details/97191896

就用node{u,v,id,l} 表示一条从u到v的长度为 l 的路径，编号为id（没加这个id之前因为插入set失败导致RE3发。

然后我们只需要枚举从1到maxk小的路径出来就行了。

每次枚举出当前最短路径，从set中删掉，然后枚举v的每条出边，看能否插入set中，如果不能插入，立刻break，由于每个点的出边是从小到大排序的，所以如果当前的不行，后面的也不行了。

#include<bits/stdc++.h>
#define maxl 50010
using namespace std;

int n,m,q,ssz,mxk,tot;
int k[maxl];
struct node
{
    int u,v,id;
    long long l;
    bool operator < (const node &b)const
    {
        if(l==b.l)
        {
            /*if(u==b.u)
                return v<b.v;
            else
                return u<b.u;*/
            return id<b.id;
        }
        else
            return l<b.l;
    }
    bool operator > (const node &b)const
    {
        if(l==b.l)
        {
            /*if(u==b.u)
                return v>b.v;
            else
                if(v==b.v)
                    return id<*/
            return id<b.id;
        }
        else
            return l>b.l;
    }
    bool operator == (const node &b)const
    {
        return u==b.u && v==b.v && l==b.l && id==id;
    }
};
struct ed
{
    int to,l;
};
set <node> s;
set <node> :: iterator it;
vector <ed> e[maxl];
node ans[maxl];

inline bool cmp(const ed &x,const ed &y)
{
    return x.l<y.l;
}

inline void prework()
{
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=n;i++)
        e[i].clear();
    int u,v,w;
    s.clear();tot=0;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&u,&v,&w);
        e[u].push_back(ed{v,w});
        s.insert(node{u,v,++tot,1ll*w});
    }
    mxk=0;
    for(int i=1;i<=q;i++)
    {
        scanf("%d",&k[i]);
        mxk=max(mxk,k[i]);
    }
    for(int i=1;i<=n;i++)
        sort(e[i].begin(),e[i].end(),cmp);
}

inline void mainwork()
{
    ssz=m;
    while(ssz>mxk)
    {
        it=s.end();
        --it;
        s.erase(it);ssz--;
    }
    int l;node d,dd,mx;
    for(int i=1;i<=mxk;i++)
    {
        if(s.begin()==s.end())
            break;
        d=*(s.begin());
        ans[i]=d;
        s.erase(s.begin());ssz--;
        if(i==mxk)
            break;
        dd.u=d.u;l=e[d.v].size();
        for(int j=0;j<l;j++)
        {
            dd.v=e[d.v][j].to;
            dd.l=d.l+e[d.v][j].l;
            if(ssz+i<mxk)
            {
                dd.id=++tot;
                s.insert(dd),ssz++;
            }
            else
            {
                it=s.end();
                --it;
                mx=(*it);
                if(dd.l<mx.l)
                {
                    dd.id=++tot;
                    s.erase(it);
                    s.insert(dd);
                }
                else
                    break;
            }
        }
    }
}

inline void print()
{
    for(int i=1;i<=q;i++)
        printf("%lld\n",ans[k[i]].l);
}

int main()
{
    int t;
    scanf("%d",&t);
    for(int i=1;i<=t;i++)
    {
        prework();
        mainwork();
        print();
    }
    return 0;
}