Luogu P1339 – 单源最短路

PROBLEM

https://www.luogu.org/problemnew/show/P1339

ANALYSIS

裸题 ，保存模板

时间复杂度：

• SPFA O(k*E)  , k 为每个节点进入队列的次数，一般小于等于2，最坏情况为O(V*E)
• Dijkstra(Heap) O(2*E+V*lgV)
• Dijkstra(Ordinary) O(n^2)

SOLUTION

// dij 55ms / 1.14MB
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>

using namespace std;

constexpr int N = 7000;
using pii = pair<int, int>;
vector<pii> z[N];
priority_queue<pii, vector<pii>, greater<pii>> q;
int n, m, from, to, d[N];
bool v[N];

int main() {
    memset(d, 0x3f, sizeof(d));
    scanf("%d%d%d%d", &n, &m, &from, &to);
    for (int i = 0, a, b, c; i < m; i++) {
        scanf("%d%d%d", &a, &b, &c);
        z[a].push_back(make_pair(b, c));
        z[b].push_back(make_pair(a, c));
    }
    q.push(make_pair(0, from));
    d[from] = 0;
    int u, r, t;
    pii p;
    while (!q.empty()) {
        p = q.top();
        q.pop();
        u = p.second;
        if (v[u]) {
            continue;
        }
        v[u] = true;
        for (auto e : z[u]) {
            r = e.first;
            t = e.second;
            if (!v[r] && d[r] > d[u] + t) {
                d[r] = d[u] + t;
                q.push(make_pair(d[r], r));
            }
        }
    }
    cout << d[to] << endl;
    return 0;
}

// spfa 45ms /  1.03MB
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>

using namespace std;

constexpr int N = 7000;
using pii = pair<int, int>;
vector<pii> z[N];
queue<int> q;
int n, m, from, to, d[N];
bool inq[N];

int main() {
    memset(d, 0x3f, sizeof(d));
    scanf("%d%d%d%d", &n, &m, &from, &to);
    for (int i = 0, a, b, c; i < m; i++) {
        scanf("%d%d%d", &a, &b, &c);
        z[a].push_back(make_pair(b, c));
        z[b].push_back(make_pair(a, c));
    }
    q.push(from);
    d[from] = 0;
    inq[from] = 1;
    int u, r, t;
    while (!q.empty()) {
        u = q.front();
        for (auto e : z[u]) {
            r = e.first;
            t = e.second;
            if (d[r] > d[u] + t) {
                d[r] = d[u] + t;
                if (!inq[r]) {
                    q.push(r);
                    inq[r] = 1;
                }
            }
        }
        inq[u] = 0;
        q.pop();
    }
    cout << d[to] << endl;
    return 0;
}

// spfa 45ms /  1.03MB
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <map>

using namespace std;

constexpr int N = 7000;
//using pii = pair<int, int>;
//vector<pii> z[N];
map<int, map<int, int>> z;
queue<int> q;
int n, m, from, to, d[N];
bool inq[N];

int main() {
    memset(d, 0x3f, sizeof(d));
    scanf("%d%d%d%d", &n, &m, &from, &to);
    for (int i = 0, a, b, c; i < m; i++) {
        scanf("%d%d%d", &a, &b, &c);
        //z[a].push_back(make_pair(b, c));
        //z[b].push_back(make_pair(a, c));
        z[a][b] = c;
        z[b][a] = c;
    }
    q.push(from);
    d[from] = 0;
    inq[from] = 1;
    int u, r, t;
    while (!q.empty()) {
        u = q.front();
        for (auto e : z[u]) {
            r = e.first;
            t = e.second;
            if (d[r] > d[u] + t) {
                d[r] = d[u] + t;
                if (!inq[r]) {
                    q.push(r);
                    inq[r] = 1;
                }
            }
        }
        inq[u] = 0;
        q.pop();
    }
    cout << d[to] << endl;
    return 0;
}

本作品使用基于以下许可授权：Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.