2019CCPC网络赛 HDU6705

题意：给出n个点m条边的有向图，问图上第K短路的长度是多少（这里的路可以经过任何重复点重复边）。

解法：解法参考https://blog.csdn.net/Ratina/article/details/100066384这位大佬的。

比赛的时候也能想到用类似Dijkstra的做法用优先队列一条一条路拓展出来但是这样会MLE也没想到解决办法。后来看了题解才学会这个比较巧妙的优化办法。

朴素的办法就是向堆优化的Dijkstra一样把(u,dist)存入优先队列里然后每次从队列中找一个最小的dist出来拓展其他边，第k次出队的就是第k短路，直至找到答案。这种办法会获得MLE。因为每次取出来拓展的边实在是太多了，空间根本存不下。你可能会想到其实优先队列最多存K个状态就好了多余的直接踢掉，那么可以用Set来实现这个只存K个状态的功能，但是遗憾的是这样会获得TLE。

正确的解法是先对全部点的出边按长度从小到大排序，减少每次取出来后拓展的状态，优先队列里存(u,v,cur,dist)状态，代表从u走到v走的是u第cur条出边且到v点的路径长度是dist。那么这个状态只拓展出两种状态，①u走第cur+1条出边到达新的v，②是v继续往下走但是只走v的第一条出边。显然这两种情况是紧接着取出来的状态的且数量变得更少。于是此题获得AC。

#include<bits/stdc++.h>

using namespace std;

const int N=5e4+;

typedef  long long LL;

int n,m,l,Max,qu[N];

LL ans[N];

struct edge{

    int x,y,z;

    bool operator < (const edge &rhs) const {

        return z<rhs.z;

    }

};

vector<edge> G[N];

struct dat{

    LL u,v,cur,dis;

    bool operator < (const dat &rhs) const {

        return dis>rhs.dis;

    }

};

priority_queue<dat> q;

void Dijkstra() {

    while (!q.empty()) q.pop();

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

        if (G[i].size()) q.push((dat){G[i][].x,G[i][].y,,G[i][].z});

    int num=;

    while (!q.empty()) {

        dat x=q.top(); q.pop();

        ans[++num]=x.dis;

        if (num>=Max) break;

        if (x.cur+<G[x.u].size())

            q.push((dat){x.u,G[x.u][x.cur+].y,x.cur+,x.dis+G[x.u][x.cur+].z-G[x.u][x.cur].z});

        for (int i=;i<G[x.v].size();i++) {

            edge e=G[x.v][i];

            q.push((dat){x.v,e.y,,x.dis+e.z});

            break;

        }

    }

}

int main()

{

    int T; cin>>T;

    while (T--) {

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

        for (int i=;i<=n;i++) G[i].clear();

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

            int x,y,z; scanf("%d%d%d",&x,&y,&z);

            G[x].push_back((edge){x,y,z});

        }

        for (int i=;i<=n;i++) sort(G[i].begin(),G[i].end());

        Max=;

        for (int i=;i<=l;i++) scanf("%d",&qu[i]),Max=max(Max,qu[i]);

        Dijkstra();

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

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

    }

    return ;

}

巴特西

2019CCPC网络赛 HDU6705 - path K短路

最新文章

热门文章