C语言 【C with STL】单源最短路之dijkstra算法

[JiansYuan]

呃呃呃
[MD] ```cpp #include <bits/stdc++.h> using namespace std; const int N = 1008600; vector<pair<long long, long long> > g[N]; long long d[N]; bool vis[N]; priority_queue<pair<long long, long long> > q; int main(){ memset(vis, false, sizeof vis); long long n, m, s; scanf("%lld %lld %lld", &n, &m, &s); for(long long i = 1; i <= n; i++) d[i] = 2147483647; for(long long i = 0; i < m; i++) { long long u, v, w; scanf("%lld %lld %lld", &u, &v, &w); g[u].push_back({v, w}); } d[s] = 0; q.push({0, s}); while(!q.empty()) { long long u = q.top().second; q.pop(); if(vis[u]) continue; vis[u] = true; for(size_t i = 0; i < g[u].size(); i++) { long long v = g[u][i].first, w = g[u][i].second; if(d[v] > d[u] + w) { d[v] = d[u] + w; q.push({-d[v], v}); } } } for(long long i = 1 ; i <= n; i++) printf("%lld ", d[i]); return 0; } ``` [/i][/u][/u][/i][/u][/i][/u][/u][/u][/u][/s][/u][/i][/MD]