fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. # define _z ios_base::sync_with_stdio(false); cin.tie(NULL);
  5. # define ll long long int
  6. #define mod 1000000007
  7.  
  8. int n;
  9. set<pair<int, int>> dist;
  10.  
  11. void dij(vector<pair<int, int>> tree[], int decided[], int d[], vector<int>path[]) {
  12.     int mindist=INT_MAX, ind=0;
  13.     auto it=dist.begin();
  14.     if (it == dist.end())
  15.     {
  16.     	cerr << "Oh snap!";
  17.     	exit(-1);
  18.     }
  19.     ind=it->second;
  20.     cout<<"inbetween"<<endl;
  21.     it=dist.erase(it);
  22.     cout<<"inbetween"<<endl;
  23.     decided[ind]=1;
  24.     for(int i=0; i<tree[ind].size(); i++) {
  25.         int update=d[ind]+tree[ind][i].second;
  26.         int previous=d[tree[ind][i].first];
  27.         if(update<previous) {
  28.             pair<int, int>p=make_pair(previous, tree[ind][i].first);
  29.             dist.erase(dist.find(p));
  30.             p=make_pair(update, tree[ind][i].first);
  31.             dist.insert(p);
  32.             path[tree[ind][i].first]=path[ind];
  33.             cout<<*path[tree[ind][i].first].begin()<<endl;
  34.             path[tree[ind][i].first].push_back(tree[ind][i].first);
  35.         }
  36.         d[tree[ind][i].first]=min(update, previous);
  37.     }
  38. }
  39.  
  40. int main()
  41. {
  42.     int edges;
  43.     cin>>n>>edges;
  44.     vector<pair<int, int>> graph[n];
  45.     set<pair<int, int>> dist;
  46.     for(int i=0; i<edges; i++) {
  47.         int x, y, weight;
  48.         cin>>x>>y>>weight;
  49.         x--; y--;
  50.         graph[x].push_back({y, weight});
  51.         graph[y].push_back({x, weight});
  52.     }
  53.     int src=1;
  54.     //cin>>src;
  55.     cout<<"here"<<endl;
  56.     src--;
  57.     int d[n];
  58.     for(int i=0; i<n; i++) {
  59.         if(src==i) {
  60.             dist.insert({0, i});
  61.             d[i]=0;
  62.         }
  63.         else {
  64.             dist.insert({INT_MAX, i});
  65.             d[i]=INT_MAX;
  66.         }
  67.     }
  68.     int decided[n]={0};
  69.     vector<int> path[n];
  70.     path[src].push_back(src);
  71.     for(int i=0; i<n; i++) dij(graph, decided, d, path);
  72.     if(path[n-1].begin()==path[n-1].end()) cout<<-1<<endl;
  73.     for(auto it=path[n-1].begin(); it!=path[n-1].end(); it++) cout<<*it+1<<" ";
  74.     cout<<endl;
  75. }
  76.  
Runtime error #stdin #stdout #stderr 0s 4924KB
comments (?)
stdin
copy 
5 6
1 2 2
2 5 5
2 3 4
1 4 1
4 3 3
3 5 1
stdout
copy 
here
stderr
copy 
Oh snap!
https://ideone.com/5NY0q3
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!