ccpc20190823

http://acm.hdu.edu.cn/showproblem.php?pid=6705

分析；先把每条边以形式放进堆，堆按路径权值从小到大排序，然后每次取出堆顶，用v的出边扩展新的路径。但是一个点的出度可能会非常大（如菊花图），可以发现，将出边排序之后，

每次只需要扩展当前点最小的出边，和扩展到当前点的边的下一条边即可。堆中需要记录当前结点，当前距离，上一节点距离，扩展到当前节点时下一条应该扩展的边。

（注意，如果一次性扩展当前点连出去的所有权值相同的边，是会TLE的，实际上也是没有必要的。）
复杂度：O（k*log（m+k））

#include<queue>

#include<vector>

#include<algorithm>

#include<cstdio>

#include<cstring>

using namespace std;

typedef long long ll;

#define pb push_back

const int M=1e5+;

struct node{

    ll cost;

    int u,id;

    node(ll costt=,int uu=,int idd= ){

        cost=costt;

        u=uu;

        id=idd;

    }

    bool operator < ( const node &b)const{

        return cost>b.cost;

    }

};

#define pli pair<ll,int>

vector<pli> e[M];

ll ans[M];

int a[M];

priority_queue<node> que;

int main(){

    int t;

    scanf("%d",&t);

    while(t--){

        int n,m,q;

        scanf("%d%d%d",&n,&m,&q);

        for(int i=;i<=n;i++)

            e[i].clear();

        while(!que.empty())

            que.pop();

        for(int i=;i<=m;i++){

            int u,v;

            ll w;

            scanf("%d%d%lld",&u,&v,&w);

            e[u].pb(pli(w,v));

        }

        int maxxk=;

        for(int i=;i<=q;i++){

            scanf("%d",&a[i]);

            maxxk=max(maxxk,a[i]);

        }

        for(int i=;i<=n;i++)

            sort(e[i].begin(),e[i].end());

        for(int i=;i<=n;i++)

            if(e[i].size())

                que.push(node(e[i][].first,i,));

        int tot=;

        while(!que.empty()){

            node now=que.top();

            que.pop();

            int u=now.u;

            int id=now.id;

            ll Cost=now.cost;

            if(Cost)

                ans[++tot]=Cost;

            if(tot==maxxk)

                break;

            if(id<(int)e[u].size()-)

                que.push(node(Cost-e[u][id].first+e[u][id+].first,u,id+));

            int v=e[u][id].second;

            if(e[v].size())

                que.push(node(Cost+e[v][].first,v,));

        }

        for(int i=;i<=q;i++)

            printf("%lld\n",ans[a[i]]);

    }

    return ;

}

巴特西

ccpc20190823

最新文章

热门文章