fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define all(x)     (x).begin(),(x).end()
  3. #define allr(x)    x.rbegin(),x.rend()
  4. #define sz(x)      ((int)x.size())
  5. #define Debug(x)      cout<<#x<<" = "<<x<<endl
  6. #define AbdElmawla std::ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  7. #include <ext/pb_ds/assoc_container.hpp>
  8. #include <ext/pb_ds/tree_policy.hpp>
  9. #define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
  10. #define S second
  11. #define F first
  12. using namespace __gnu_pbds;
  13. using namespace std;
  14. typedef unsigned long long int ull;
  15. typedef long long ll;
  16. typedef long double ld;
  17. int dx[]= {-1,1,0,0,1,-1,1,-1,0};
  18. int dy[]= {0,0,1,-1,1,-1,-1,1,0};
  19. int dx2[]= {-1,0,1,0};
  20. int dy2[]= {0,1,0,-1};
  21. void files()
  22. {
  23. #ifndef ONLINE_JUDGE
  24.     freopen("input.txt", "r", stdin);
  25.     freopen("output.txt", "w", stdout);
  26. #endif // ONLINE_JUDGE
  27. }
  28. vector<vector<pair<int,pair<double,double>>>>adj(101);
  29. vector<pair<double,double>>dis(101);
  30. vector<int>pre(101);
  31. struct edge
  32. {
  33.     int from,to;
  34.     double t,d;
  35.     edge(int from,int to,double t,double d):from(from),to(to),d(d),t(t) {}
  36.     bool operator<(const edge&e)const
  37.     {
  38.         if(e.t==t)
  39.             return e.d<d;
  40.         return e.t<t;
  41.     }
  42. };
  43. void Dijkstra(int s)
  44. {
  45.     priority_queue<edge>pq;
  46.     pq.push(edge(-1,s,0,0));
  47.     dis[s]= {0,0};
  48.     while(!pq.empty())
  49.     {
  50.         auto e=pq.top();
  51.         pq.pop();
  52.         if(e.t>dis[e.to].F||(e.t==dis[e.to].F&&e.d>dis[e.to].S))
  53.             continue;
  54.         pre[e.to]=e.from;
  55.         for(auto &it:adj[e.to])
  56.         {
  57.             if(dis[it.F].F>max(e.t,it.S.F)||(dis[it.F].F==max(e.t,it.S.F)&&dis[it.F].S>it.S.S+e.d))
  58.             {
  59.                 dis[it.F].F=max(e.t,it.S.F);
  60.                 dis[it.F].S=it.S.S+e.d;
  61.                 pq.push(edge(e.to,it.F,dis[it.F].F,dis[it.F].S));
  62.             }
  63.         }
  64.     }
  65.     return;
  66. }
  67. int main()
  68. {
  69.     AbdElmawla
  70.     files();
  71.     /*---------------------------------------*/
  72.  
  73.     int x,y,n,t,s,e;
  74.     double c,d;
  75.     while(cin>>n)
  76.     {
  77.         cin>>t>>s>>e;
  78.         s--,e--;
  79.         for(int i=0; i<n; i++)
  80.             adj[i].clear(),dis[i]= {1e9,1e9};
  81.         while(t--)
  82.         {
  83.             cin>>x>>y>>c>>d;
  84.             adj[x-1].push_back({y-1,{c,d}});
  85.             adj[y-1].push_back({x-1,{c,d}});
  86.         }
  87.         Dijkstra(s);
  88.         stack<int>st;
  89.         t=e;
  90.         while(e!=s){
  91.             st.push(e);
  92.             e=pre[e];
  93.         }
  94.         cout<<s+1;
  95.         while(!st.empty())cout<<' '<<st.top()+1,st.pop();
  96.         cout<<fixed<<setprecision(1)<<'\n'<<dis[t].S<<' '<<dis[t].F<<'\n';
  97.     }
  98. }
  99.  
Success #stdin #stdout 0.01s 5360KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/F5aJ8t
language:
C++ (gcc 8.3)
created:
1 year 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!