fork download
copy 
  1. //#pragma GCC optimize("Ofast,unroll-loops")
  2. //#pragma GCC target("avx2,tune=native")
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5.  
  6. #define file "o"
  7. #define ff(i, a, b) for(auto i=(a); i<=(b); ++i)
  8. #define ffr(i, b, a) for(auto i=(b); i>=(a); --i)
  9. #define nl "\n"
  10. #define ss " "
  11. //#define pb push_back
  12. #define pb emplace_back
  13. #define fi first
  14. #define se second
  15. #define sz(s) (int)s.size()
  16. #define all(s) (s).begin(), (s).end()
  17. #define ms(a,x) memset(a, x, sizeof (a))
  18. #define cn continue
  19. #define re exit(0)
  20.  
  21. typedef long long ll;
  22. typedef unsigned long long ull;
  23. typedef long double ld;
  24. typedef vector<int> vi;
  25. typedef vector<ll> vll;
  26. typedef pair<int, int> pii;
  27. typedef pair<ll, ll> pll;
  28. typedef vector<pii> vpii;
  29. typedef vector<pll> vpll;
  30.  
  31. const int mod=1e9+7;
  32. const int maxn=2e5+15;
  33. const ll inf=4e18;
  34.  
  35. mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  36. ll ran(ll l, ll r)
  37. {
  38.     return uniform_int_distribution<ll> (l, r)(rng);
  39. }
  40.  
  41. inline void rf(){
  42.     ios_base::sync_with_stdio(false);
  43.     cin.tie(nullptr); cout.tie(nullptr);
  44.     if(fopen(file".inp","r")){
  45.         freopen(file".inp","r",stdin); freopen(file".out","w",stdout);
  46.     }
  47. }
  48.  
  49. template<typename T> inline void add(T &x, const T &y)
  50. {
  51.     x+=y;
  52.     if(x>=mod) x-=mod;
  53.     if(x<0) x+=mod;
  54. }
  55.  
  56. template<typename T> inline bool maxi(T &a, T b)
  57. {
  58.     if(a>=b) return 0;
  59.     a=b; return 1;
  60. }
  61.  
  62. template<typename T> inline bool mini(T &a, T b)
  63. {
  64.     if(a<=b) return 0;
  65.     a=b; return 1;
  66. }
  67.  
  68. int n, m;
  69. int par[maxn], sz[maxn];
  70. struct edge{int u, v; ll p, w;} e[300005];
  71. vector<pair<int, ll>> g[maxn];
  72. ll d[maxn];
  73. priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> q;
  74.  
  75. inline bool cmp(edge x, edge y)
  76. {
  77.     return x.p<y.p;
  78. }
  79.  
  80. inline int fp(int u)
  81. {
  82.     if(u==par[u]) return par[u];
  83.     return par[u]=fp(par[u]);
  84. }
  85.  
  86. inline bool unite(int u, int v)
  87. {
  88.     u=fp(u); v=fp(v);
  89.     if(u==v) return 0;
  90.     if(sz[u]>sz[v]) swap(u, v);
  91.     sz[v]+=sz[u]; par[u]=v;
  92.     return 1;
  93. }
  94.  
  95. inline bool lt(int u, int v)
  96. {
  97.     return fp(u)==fp(v);
  98. }
  99.  
  100. void djk()
  101. {
  102.     ff(i, 1, n) d[i]=inf;
  103.     d[1]=0; q.push({0, 1});
  104.     while(!q.empty())
  105.     {
  106.         pair<ll, int> tmp=q.top(); q.pop();
  107.         ll du=tmp.fi; int u=tmp.se;
  108.         if(du!=d[u]) cn;
  109.         for(auto x:g[u])
  110.         {
  111.             int v=x.fi; ll w=x.se;
  112.             if(mini(d[v], du+w)) q.push({d[v], v});
  113.         }
  114.     }
  115. }
  116.  
  117. signed main()
  118. {
  119.     rf();
  120.     cin>>n>>m;
  121.     ff(i, 1, n) par[i]=i, sz[i]=1;
  122.     ff(i, 1, m)
  123.     {
  124.         int u, v; ll p, w; cin>>u>>v>>p>>w;
  125.         e[i]={u, v, p, w};
  126.     }
  127.     sort(e+1, e+m+1, cmp);
  128.     ff(i, 1, m)
  129.     {
  130.         int u=e[i].u, v=e[i].v; ll w=e[i].w;
  131.         unite(u, v);
  132.         g[u].pb(v, w); g[v].pb(u, w);
  133.         if(lt(1, n))
  134.         {
  135.             cout<<e[i].p<<ss;
  136.             int j=i+1;
  137.             while(j<=m && e[j].p==e[i].p)
  138.             {
  139.                 u=e[j].u; v=e[j].v; w=e[j].w;
  140.                 g[u].pb(v, w); g[v].pb(u, w);
  141.                 ++j;
  142.             }
  143.             break;
  144.         }
  145.     }
  146.     djk(); cout<<d[n];
  147.     re;
  148. }
  149.  
Success #stdin #stdout 0.01s 9744KB
comments (?)
stdin
copy 
5 7
1 2 1 1
1 3 2 3
2 3 3 1
2 4 1 2
2 5 1 3
3 5 1 1
4 5 1 2
stdout
copy 
1 4
https://ideone.com/B8pboG
language:
C++14 (gcc 8.3)
created:
8 days 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!