Untitled
unknown
plain_text
a year ago
1.7 kB
6
Indexable
#include <bits/stdc++.h> using namespace std; typedef long long int ll; #define endl "\n" const double PI = 3.14159265358979; const ll INF = 1e18 + 7; const ll MOD = 1e9 + 7; const ll nax = 2505; const int LOG = 25; vector<ll> dijkstra(int src, vector<pair<ll, int> > adj[], int n) { vector<ll> distance(n + 1, INF); vector<bool> visited(n + 1, false); priority_queue<pair<ll, int> > pq; distance[src] = 0; pq.push({-distance[src], src}); while(!pq.empty()) { pair<ll, int> current = pq.top(); pq.pop(); int currentNode = current.second; ll currentDistance = -current.first; if (visited[currentNode]) { continue; } visited[currentNode] = true; for (auto &neighbour: adj[currentNode]) { ll neighbourDistance = neighbour.second; int neighbourNode = neighbour.first; if (distance[neighbourNode] > currentDistance + neighbourDistance) { distance[neighbourNode] = currentDistance + neighbourDistance; pq.push({-distance[neighbourNode], neighbourNode}); } } } return distance; } void solve() { int n, m; cin >> n >> m; vector<pair<ll, int > > adj[n + 1]; for (int i = 1; i <= m; i++) { int x, y, z; cin >> x >> y >> z; adj[x].push_back({y, z}); // adj[y].push_back({x, z}); } vector<ll> distance = dijkstra(1, adj, n); for (int i = 1; i <= n; i++) { cout << distance[i] << " "; } } signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); // int t; cin >> t; while(t--) solve(); return 0; }
Editor is loading...
Leave a Comment