Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- // #include<iostream>
- using namespace std;
- typedef long long ll;
- ll const INF=1e15;
- void dijkstra(ll N, ll M, ll S, vector<pair<ll, ll>> adj_list[], vector<ll> &dist)
- {
- // distance, node_id
- priority_queue<pair<ll,ll>, vector<pair<ll,ll>>, greater<pair<ll,ll>>> pq;
- dist[S] = 0;
- pq.push({0, S});
- while(! pq.empty())
- {
- pair<ll, ll> front_pair = pq.top();
- pq.pop();
- ll curr_dist = front_pair.first;
- ll curr_node = front_pair.second;
- for (auto &ed: adj_list[curr_node])
- {
- ll neigh_node = ed.first;
- ll neigh_dist = curr_dist + ed.second;
- if (dist[neigh_node] > neigh_dist)
- {
- dist[neigh_node] = neigh_dist;
- pq.push({dist[neigh_node], neigh_node});
- }
- }
- }
- }
- int main()
- {
- ll T, N, M, S;
- cin >> T;
- while (T--){
- cin >> N >> M;
- vector<pair<ll, ll>> adj_list[N];
- for (ll i = 0; i < M; ++i)
- {
- ll x, y, dist;
- cin >> x >> y >> dist;
- adj_list[x-1].push_back({y-1, dist});
- adj_list[y-1].push_back({x-1, dist});
- }
- cin >> S;
- --S;
- vector<ll> dist(N + 1, INF);
- dijkstra(N, M, S, adj_list, dist);
- for(int i=0; i < N; ++i)
- {
- if (dist[i] >= INF) dist[i] = -1;
- if (i != S) cout << dist[i] << " ";
- }
- cout << "\n";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement