洛谷 p4779
#include <iostream> #include <vector> #include <stack> #include <list> #include <map> #include <set> #include <deque> #include <queue> #include <cstring> #include <unordered_map> #include <unordered_set> #include <algorithm> #include <numeric> #include <chrono> #include <ctime> #include <cmath> #include <cctype> #include <string> #include <cstdio> #include <iomanip> #include <thread> #include <mutex> #include <condition_variable> #include <functional> #include <iterator> using namespace std; const int MAXN = 1e5+7 ,MAXM = 500007; const int INF = 0x7fffffff; struct Edge { int to, w,next; Edge() : to(0), w(0) ,next(0){} }nodes[MAXM]; int heads[MAXN ] = {0}, d[MAXN] = { 0 }, visit[MAXN] = { 0 }, nCount = 0, n = 0, m = 0, s = 0; void AddEdge(int from, int to, int widght) { nodes[++nCount].to = to; nodes[nCount].w = widght; nodes[nCount].next = heads[from]; heads[from] = nCount; } void Dijkstra(int s) { for (int i = 1; i <= n; ++i) d[i] = INF; d[s] = 0; priority_queue<pair<int, int> ,vector<pair<int,int> > ,greater<pair<int,int> > > que; que.push(make_pair(0, s)); while (!que.empty()) { pair<int, int> temp = que.top(); que.pop(); int u = temp.second; if (visit[u]) continue;; visit[u] = true; for (int i = heads[u]; i; i = nodes[i].next) { int v = nodes[i].to; if (d[v] > d[u] + nodes[i].w) { d[v] = d[u] + nodes[i].w; if(!visit[v]) que.push( make_pair( d[v], v ) ); } } } } int main() { cin >> n >> m >> s; int a, b, c; for (int i = 1; i <= m; ++i) { cin >> a >> b >> c; AddEdge(a, b, c); } Dijkstra(s); for (int i = 1; i <= n; ++i) { cout << d[i] << " "; } return 0; }