题目描述

大根堆 不用C++11

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

// AcWing 850. Dijkstra求最短路 II
#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

typedef pair<int, int> PII;

const int N = 1.5e5 + 10, INF = 0xc0c0c0c0;

int n, m;
int h[N], e[N], ne[N], w[N], idx;
int dist[N];
bool st[N];

void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}

int dijkstra() {
    memset(dist, 0xc0, sizeof dist);    // 赋最小值
    dist[1] = 0;

    priority_queue<PII> heap;
    heap.push(make_pair(0, 1)); // first存储距离，second存储节点编号

    while (!heap.empty()) {
        PII t = heap.top();
        heap.pop();

        int ver = t.second, distance = t.first;

        if (st[ver]) continue;
        st[ver] = true;

        for (int i = h[ver]; i != -1; i = ne[i]) {
            int j = e[i];
            if (dist[j] < dist[ver] + w[i]) { // 例如 4 > 3 变成负数需要 -4 < -3
                dist[j] = dist[ver] + w[i];
                heap.push(make_pair(dist[j], j));
            }
        }
    }

    if (dist[n] == INF) return -1;
    else return -dist[n];
}

int main() {
    scanf("%d %d", &n, &m);

    memset(h, -1, sizeof h);

    while (m --) {
        int x, y, z;
        scanf("%d %d %d", &x, &y, &z);
        add(x, y, -z);  // 距离全部存成负数
    }

    printf("%d", dijkstra());

    return 0;

}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla