HDU-6705 path (图上不固定起点终点的第k短路)

题意

给出一个有向图，$q$次询问图上第$k$短的路径长度(任意起点终点)。

思路

算法思想和Dijkstra算法有点像，把每条边$(u, v, w)$放进优先队列，队列按路径长度从小到大排序，然后每次取出队首，用$v$的出边扩展新的路径，放进队列，这样第i次取出的边就是第i短的。但是一个点的出度可能会非常大(比如菊花图)，这样每次出队一个却入队很多个，会导致MLE。

可作如下更改(为方便描述，将路径最后一条边记为$e(u,v)$)，将每个结点的出边按边权从小到大排序，优先队列中的元素为路径，元素记录路径长度、$u$、$e$是$u$的第几条出边。可以发现，每次只需要扩展$v$最小的出边，和以$u$为始点的$e$的下一条边即可。

时间复杂度：$O(k*log(m+k))$

代码实现

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <utility>
#include <algorithm>
const int N = 50010;
int query[N], ans[N];
struct Node
{
    int len, u, id;
    Node (int _len = 0, int _u = 0, int _id = 0) {
        len = _len, u = _u, id = _id;
    }
    bool operator < (const Node &b) const{
        return len > b.len;
    }
};

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int n, m, q;
        std::vector<std::pair<int, int> > G[N];
        memset(ans, 0, sizeof(ans));
        scanf("%d %d %d", &n, &m, &q);
        for (int i = 0, u, v, w; i < m; i++) {
            scanf("%d %d %d", &u, &v, &w);
            G[u].push_back(std::make_pair(w, v));
        }
        for (int i = 1; i <= n; i++) std::sort(G[i].begin(), G[i].end());
        int mx = 0;
        for (int i = 0; i < q; i++) {
            scanf("%d", &query[i]);
            mx = std::max(query[i], mx);
        }
        std::priority_queue<Node> que;
        for (int i = 1; i <= n; i++) {
            if (G[i].size()) que.push(Node(G[i][0].first, i, 0));
        }
        int cnt = 0;
        while (!que.empty()) {
            Node no = que.top();
            que.pop();
            int u = no.u, id = no.id, len = no.len;
            ans[++cnt] = len;
            if (cnt == mx) break;
            if (id < (int)G[u].size() - 1) {
                que.push(Node(len - G[u][id].first + G[u][id+1].first, u, id + 1));
            }
            int v = G[u][id].second;
            if (G[v].size()) {
                que.push(Node(len + G[v][0].first, v, 0));
            }
        }
        for (int i = 0; i < q; i++) printf("%d
", ans[query[i]]);
    }
    return 0;
}

View Code