求条 $Dijkstra$

#include <bits/stdc++.h>
using namespace std;
#define mp(p, q) make_pair(p, q)
const int maxn = 1e5 + 10;
const int inf = 0x7fffffff;
int n, m, s, dis[maxn];
bool vis[maxn];
vector<pair<int, int>> e[maxn];
queue<int> que;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n >> m >> s;
    for (int i = 1; i <= m; i++) {
        int u, v, w; cin >> u >> v >> w;
        e[u].push_back(mp(v, w));
    }
    // all the nodes' distance are inf
    for (int i = 1; i <= n; i++) dis[i] = inf;
    dis[s] = 0; vis[s] = true; que.push(s); 
    for (int i = 0; i < e[s].size(); i++) 
        dis[e[s][i].first] = dis[s] + e[s][i].second;
    while (1) {
        int q = inf, mn = inf;
        for (int i = 1; i <= n; i++) 
            if (!vis[i]) mn = min(mn, dis[i]);
        for (int i = 1; i <= n; i++) 
            if (!vis[i] && dis[i] == mn) { q = i; break; }
        if (q == inf) break;
        vis[q] = true;
        for (int i = 0; i < e[q].size(); i++) 
            dis[e[q][i].first] = min(dis[e[q][i].first], dis[q] + e[q][i].second);
    }
    for (int i = 1; i <= n; i++) cout << dis[i] << " ";
    cout << "\n";
    return 0;
}