Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- #include <list>
- #include <queue>
- #include <cstring>
- #define ll long long
- #define ps push_back
- using namespace std;
- struct node{
- int idx;
- ll shortest_path;
- node(int i,ll s){
- idx = i;
- shortest_path = s;
- }
- bool operator < (const node &tmp) const {
- return shortest_path > tmp.shortest_path;
- }
- };
- vector<pair<int,int>> graph[100050];
- int main() {
- int n,m;
- cin >>n >> m;
- for(int i = 0;i<m;i++){
- ll a,b,c;
- cin >> a >> b>> c;
- graph[a].push_back(make_pair(b, c));
- // graph[b].push_back(make_pair(a, c));
- }
- priority_queue<node> pq;
- vector<ll> dist(n+1,1e18);
- vector<bool> visited(n+1,false);
- dist[1] = 0;
- pq.push(node(1,0));
- while(!pq.empty()){
- node curr = pq.top();
- pq.pop();
- if(visited[curr.idx]) continue;
- visited[curr.idx] = true;
- for(int j = 0;j<graph[curr.idx].size();j++){
- int sosed = graph[curr.idx][j].first;
- ll pat = graph[curr.idx][j].second;
- if(!visited[sosed] and curr.shortest_path+pat < dist[sosed]){
- pq.push(node(sosed,curr.shortest_path+pat));
- dist[sosed] = curr.shortest_path+pat;
- }
- }
- }
- for(int i = 1;i<= n;i++){
- cout << dist[i] << " " ;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement