dijkstra

Code：

#include<bits/stdc++.h>
    
using namespace std;
typedef pair <int, int> pii;
const int N = 1e5 + 5, inf = INT_MAX;
int n, m, dis[N], s;
// struct node {
    // int from, to, w, val;
// };

bool vis[N]; vector <pii> edges[N];

void addedges (int from, int to, int w) {
    edges[from].push_back({to, w});
    // edges[to].push_back({from, w});
}

void dijkstra(int s) {
    for (int i = 1; i <= n; i++) dis[i] = inf;
    priority_queue <pii, vector <pii>, greater <pii>> pq;
    dis[s] = 0; pq.push({0, s});
    while (!pq.empty()) {
        pii now = pq.top(); pq.pop();
        int from = now.second; 
        if (vis[from]) continue;
        vis[from] = true;
        for (pii tmp : edges[from]) {
            int to = tmp.first, w = tmp.second;
            if (dis[to] > dis[from] + w) {
                dis[to] = dis[from] + w;
                pq.push({dis[to], to});
            }
        }
    }
}   

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    //cin >> n >> m; 
    cin >> n >> m >> s;
    for (int i = 1; i <= m; i++) {
        int from, to, w; cin >> from >> to >> w;
        addedges(from, to, w);
    }
    dijkstra(s);
    for (int i = 1; i <= n; i++) {
        cout << dis[i] << ' ';
    }
    return 0;
}