fork download
copy 
  1. // ROOT : DRAGON3012009
  2. #include <bits/stdc++.h>
  3. #define ll long long
  4. #define ld long double
  5. #define el "\n"
  6. #define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  7. #define __ROOT__ int main()
  8. #pragma GCC optimize("O2")
  9. #define FOR(i,l,r) for(int i = l ; i <= r ; i ++)
  10. #define FORD(i,r,l) for(int i = r ; i >= l ; i --)
  11. #define REP(i, a ) for(int i = 0 ; i < a ; i ++ )
  12. #define fi first
  13. #define se second
  14. #define M 1000000007
  15. #define MAXN 1000001
  16. #define INF (1ll<<59)
  17. #define BLOCK_SIZE 425
  18. #define MAX_NODE 1001001
  19. #define LOG 19
  20. #define ALPHA_SIZE 26
  21. #define BASE 311
  22. #define NAME "file"
  23. #define compare(v) sort((v).begin(), (v).end()); (v).erase(unique((v).begin(), (v).end()), (v).end());
  24. using namespace std;
  25. const ll MOD[] = {(ll)1e9 + 2277, (ll)1e9 + 5277, (ll)1e9 + 8277, (ll)1e9 + 9277, (ll) 1e9 + 7 };
  26. const ll NMOD = 1;
  27. const int dx[] = {-1, 0, 1,0};
  28. const int dy[] = {0, 1, 0, -1};
  29. //**Variable**//
  30. ll n, m, s,  t ;
  31. ll arr[MAXN];
  32. ll d[MAXN] ;
  33. vector<pair<ll,ll>>adj[MAXN] ;
  34. //**Struct**//
  35. struct e {
  36.     ll u, v, w ;
  37. } edge[MAXN] ;
  38. //**Function**//
  39. template<class X, class Y >
  40. bool minimize(X & x, const Y &y ) {
  41.     if(x > y ) {
  42.         x = y ;
  43.         return true ;
  44.     } else return false;
  45. }
  46. template<class X, class Y >
  47. bool maximize(X &x, const Y &y ) {
  48.     if(x < y  ) {
  49.         x = y  ;
  50.         return true;
  51.     } else return false ;
  52. }
  53.  
  54. void init() {
  55.     cin>>n>>m;
  56.     FOR(i,1, m) {
  57.         ll x, y, w ;
  58.         cin >> x>> y >> w;
  59.         edge[i].u = x ;
  60.         edge[i].v = y ;
  61.         edge[i].w = w  ;
  62.         adj[x].push_back({y, w}) ;
  63.     }
  64.     cin >> s >> t;
  65. }
  66. void dijkstra(ll st ) {
  67.     REP(i, MAXN ) d[i]= INF ;
  68.     d[st] = 0 ;
  69.     priority_queue<pair<ll,ll>, vector<pair<ll,ll>>, greater<>> pq ;
  70.     pq.push({0, st}) ;
  71.     while(!pq.empty()) {
  72.         pair<ll,ll> u = pq.top() ;
  73.         pq.pop() ;
  74.         if(d[u.se] > u.fi) continue ;
  75.         for(pair<ll,ll>  v: adj[u.se ]) {
  76.             if( minimize(d[v.fi], v.se + u.fi ) ) {
  77.                 pq.push({d[v.fi], v.fi}) ;
  78.             }
  79.         }
  80.     }
  81. }
  82. vector<ll>DAG [MAXN] ;
  83. void build_DAG() {
  84.     FOR(i, 1, m) {
  85.         if(d[edge[i].u] + edge[i].w == d[edge[i].v] ) {
  86.             DAG[edge[i].u].push_back(edge[i].v ) ;
  87.         }
  88.     }
  89. }
  90. bool check = false;
  91. vector<ll> path ;
  92. void dfs(ll u  ) {
  93.     if(u == t) check = true;
  94.     path.push_back(u);
  95.     if(check ) return ;
  96.     vector<ll> temp ;
  97.     for(ll v : DAG[u]) {
  98.         temp.push_back(v) ;
  99.     }
  100.     sort(temp.begin(), temp.end())  ;
  101.     for(ll v : temp ) {
  102.         dfs(v) ;
  103.         if(check ) return ;
  104.     }
  105.     path.pop_back() ;
  106. }
  107. void solve() {
  108.     dijkstra(s) ;
  109.     build_DAG();
  110.     dfs(s) ;
  111.     cout << d[t] << el ;
  112.     for(ll v : path ) cout << v << " " ;
  113. }
  114.  
  115. __ROOT__ {
  116. //     freopen(NAME".inp" , "r" , stdin);
  117. //     freopen(NAME".out" , "w", stdout) ;
  118.     fast;
  119.     init();
  120.     solve();
  121. }
  122.  
  123.  
  124.  
Success #stdin #stdout 0.02s 62796KB
comments (?)
stdin
copy 
 4 6
 2 1 3
 2 3 1
 3 1 10
 4 1 5
 3 4 5
 4 2 6
 2 4
stdout
copy 
6
2 3 4
https://ideone.com/Emv77e
language:
C++14 (clang 8.0)
created:
192 days ago
visibility:
secret

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!