fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. //variable
  4. #define ld long double
  5. #define ll long long
  6. #define db double
  7. #define ii pair<int,int>
  8. #define f first
  9. #define s second
  10. #define mp make_pair
  11. #define mt make_tuple
  12. //vector
  13. #define pb push_back
  14. #define all(v) v.begin(),v.end()
  15. #define len(a) (int)a.length()
  16. #define sz(a) (int)a.size()
  17. //mask
  18. #define BIT(i) (1LL<<(i))
  19. //better code, debugger
  20. #define watch(n) cerr << #n << ": " << n << endl
  21. #define debug(x) for (auto p: x) cerr<<p<<' ';cerr<<endl
  22. #define forw(i,j,z) for(int i=(int)j;i<=(int)z;i++)
  23. #define ford(i,j,z) for (int i=(int)j;i>=(int)z;i--)
  24. #define fIlE "test."
  25. //auto seed = chrono::high_resolution_clock::now().time_since_epoch().count();
  26. //mt19937 RAND(seed);
  27. const int mod = 1e9 + 7;
  28. inline int add(int u,int v){u+=v;if(u>=mod)u-=mod;return u;}
  29. inline int dec(int u,int v){u-=v;if(u<0)u+=mod;return u;}
  30. inline int mul(int u,int v){return (ll)u*v%mod;}
  31. #define tt pair<ll, int>
  32. const ll inf = 1e16;
  33. int n, m;
  34. vector<ii> a[100000 + 100];
  35. ll dist[100000 + 100];
  36. int ways[100000 + 100], Min[100000 + 100], Max[100000 + 100];
  37. void solve()
  38. {
  39.     cin >> n >> m;
  40.     while(m--){
  41.         int u, v, d;
  42.         cin >> u >> v >> d;
  43.         a[u].pb(mp(v, d));
  44.     }
  45.     priority_queue<tt, vector<tt>, greater<tt> > haha;
  46.     forw(i, 1, n)
  47.         dist[i] = inf, ways[i] = 0, Min[i] = Max[i] = 0;
  48.     haha.push(mp(dist[1] = 0, 1));
  49.     ways[1] = 1;
  50.     Min[1] = 0;
  51.     Max[1] = 0;
  52.     while(!haha.empty())
  53.     {
  54.         int u; ll d;
  55.         u = haha.top().s, d = haha.top().f;
  56.         haha.pop();
  57.         if (dist[u] < d) continue;
  58.         for (auto [v, e] : a[u])
  59.         {
  60.             if (dist[v] > e + d)
  61.             {
  62.                 dist[v] = e + d;
  63.                 ways[v] = ways[u];
  64.                 Min[v] = Min[u] + 1;
  65.                 Max[v] = Max[u] + 1;
  66.                 haha.push(mp(dist[v], v));
  67.             }
  68.             else if (dist[v] == e + d){
  69.                 ways[v] = add(ways[v], ways[u]);
  70.                 Min[v] = min(Min[v], Min[u] + 1);
  71.                 Max[v] = max(Max[v], Max[u] + 1);
  72.             }
  73.         }
  74.     }
  75.     cout << dist[n] << ' ' << ways[n] << ' ' << Min[n] << ' ' << Max[n];
  76. }
  77. signed main()
  78. {
  79.     ios_base::sync_with_stdio(false);
  80.     cin.tie(0);
  81.     if (fopen(fIlE"inp", "r"))
  82.         freopen(fIlE"inp","r",stdin), freopen(fIlE"out","w",stdout);
  83.     //time_t TIME_TU=clock();
  84.     int t=1;
  85. //    cin>>t;
  86.     while(t--)
  87.         solve();
  88.     //time_t TIME_TV=clock();
  89.     //cerr<<(db)(TIME_TV-TIME_TU)/CLOCKS_PER_SEC<<endl;
  90.     return 0;
  91. }
  92.  
Success #stdin #stdout 0.01s 7792KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0 0 0 0
https://ideone.com/06NIHT
language:
C++ (gcc 8.3)
created:
12 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!