path

解题思路

先用vector存图，然后将每个vector按照边的权值从小到大排序。将每个顶点作为起点的边里最短的边存入优先队列。对于存入优先队列的信息，应有边起点，终点，是其起点的第几短边，以及路径总长度。优先队列按照路径长度从小到大排序，每次出队当前最短的路径，对于一条路径，更新两条新的可能最短的路径，即这条路后面加上一条可走的最短边，以及这条路最后一条边换成一条次短边。将询问排序，不断更新答案即可。

代码如下

#include <bits/stdc++.h>

#define INF 0x3f3f3f3f

using namespace std;

typedef long long ll;

const int N = 100010;

struct T{

    int x, y, f;

    ll w;

    T(int x, int y, ll w, int f): x(x), y(y), w(w), f(f){}

    bool operator<(const T& a)const{

        return w > a.w;

    }

};

struct line{

    int r;

    ll w;

    line(int r, ll w): r(r), w(w){}

    bool operator<(const line& a)const{

        return w < a.w;

    }

};

vector<line> vec[N];

struct R{

    int i, k;

    bool operator<(const R& a)const{

        return k < a.k;

    }

}qy[N];

ll ans[N];

priority_queue<T> pq;

int main()

{

    int t;

    scanf("%d", &t);

    while(t --){

        int n, m, q;

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

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

            int u, v;

            ll w;

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

            vec[u].push_back(line(v, w));

        }

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

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

        }

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

            if(vec[i].size())

                pq.push(T(i, vec[i][0].r, vec[i][0].w, 0));

        }

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

            scanf("%d", &qy[i].k);

            qy[i].i = i;

        }

        sort(qy + 1, qy + q + 1);

        int cnt = 0;

        int id = 1;

        while(!pq.empty()){

            int x = pq.top().x;

            int y = pq.top().y;

            ll w = pq.top().w;

            int f = pq.top().f;

            pq.pop();

            ++cnt;

            while(id <= q && cnt == qy[id].k){

                ans[qy[id].i] = w;

                ++id;

            }

            if(id > q)

                break;

            if(vec[y].size())

                pq.push(T(y, vec[y][0].r, w + vec[y][0].w, 0));

            if(vec[x].size() > f + 1)

                pq.push(T(x, vec[x][f + 1].r, w + vec[x][f + 1].w - vec[x][f].w, f + 1));

        }

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

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

        }

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

            vec[i].clear();

        while(!pq.empty())

            pq.pop();

    }

    return 0;

}

巴特西

2019ccpc网络赛hdu6705 path

path

解题思路

代码如下

最新文章

热门文章