P4779 【模板】单源最短路径（标准版）

Link

Solution

数据比较强的模板题，回忆dijk用。

Code

#include <memory.h>
#include <algorithm>
#include <climits>
#include <cmath>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <unordered_set>
#include <vector>
#define LL long long

const double pi = 3.14;
const int maxn = 100010;

int dis[maxn], vis[maxn];
std::vector<std::pair<int, int>> G[maxn];

void dijk(int s)
{
    memset(dis, 1e9 + 100, sizeof(dis));
    dis[s] = 0;
    std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>,
                        std::greater<std::pair<int, int>>>q;
    q.push({0, s});
    while (!q.empty()) {
        int u = q.top().second;
        q.pop();
        if (!vis[u]) {
            vis[u] = 1;
            for (auto i : G[u]) {
                int v = i.first, w = i.second;
                if (dis[v] > dis[u] + w) {
                    dis[v] = dis[u] + w;
                    q.push({dis[v], v});
                }
            }
        }
    }
}

int main()
{
    int n, m, s, t, u, v, w;
    std::cin >> n >> m >> s;
    while (m--) {
        std::cin >> u >> v >> w;
        G[u].push_back(std::make_pair(v, w));
    }
    dijk(s);
    for (size_t i = 1; i <= n; i++) { std::cout << dis[i] << " "; }
    return 0;
}