G2A Many GEOs
SHARE
TWEET

Untitled

a guest Apr 4th, 2020 119 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define st first
  5. #define nd second
  6. #define pb push_back
  7. #define int long long
  8.  
  9. typedef pair<int,int> pii;
  10. typedef pair<int,pii> piii;
  11.  
  12. const int N = 1e5+5 , inf = 1e14;
  13.  
  14. int n , m , disti[N] , distf[N] , vis[N] , p[N];
  15. vector<pii> adj[N];
  16. bool ok;
  17. vector<int> vec;
  18.  
  19. void Djikstra(int u , int *dist){
  20.   priority_queue<pii , vector<pii> , greater<pii> > fila;
  21.   for(int i = 0 ; i < n ; i++) dist[i] = inf;
  22.   fila.push({0,u}) , dist[u] = 0;
  23.   while(!fila.empty()){
  24.     u = fila.top().nd , fila.pop();
  25.     for(auto v : adj[u])
  26.       if(dist[v.st] > dist[u] + v.nd)
  27.         dist[v.st] =  dist[u] + v.nd , fila.push({dist[v.st],v.st});
  28.   }
  29. }
  30.  
  31. void dfs(int u){
  32.   vis[u] = 1;
  33.   if(u == 1 || ok){ok = true; return;}
  34.   for(auto v : adj[u])
  35.     if(distf[v.st] + v.nd > distf[u]  && vis[v.st] == 0) dfs(v.st) , p[v.st] = u;
  36. }
  37.  
  38. main(){
  39.  
  40.   ios_base::sync_with_stdio(0),cin.tie(0);
  41.  
  42.   cin >> n >> m;
  43.  
  44.   memset(p,-1,sizeof(-1));
  45.   for(int i = 0 ; i < m ; i++){
  46.     int x , y , z;
  47.     cin >> x >> y >> z;
  48.     adj[x].pb({y,z}) , adj[y].pb({x,z});
  49.   }
  50.  
  51.   Djikstra(0,disti) , Djikstra(1,distf) , ok = false , dfs(0);
  52.  
  53.   if(vis[1] == 0) cout << "impossible\n";
  54.  
  55.   else{
  56.     int u = 1;
  57.     while(u != 0){vec.pb(u) , u = p[u];}
  58.     vec.pb(0);
  59.     cout << vec.size() << " ";
  60.     for(int i = vec.size() - 1 ; i >= 0 ; i--) cout << vec[i] << " ";
  61.     cout << "\n";
  62.   }
  63.  
  64. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top