fork download
copy 
  1. #include<bits/stdc++.h>
  2. #include <vector>
  3. #include <iostream>
  4. #include <algorithm>
  5. #include <string>
  6. #include <iomanip>
  7. #include <cmath>
  8. #include <ctime>
  9. #include <numeric>
  10. #include <bitset>
  11. #define endl '\n'
  12. #define ll long long
  13. #define all(n) n.begin() , n.end( )
  14. #define vi vector<int>
  15. #define vvi vector<vi>
  16. #define int long long
  17. #define pii pair<int,int>
  18. #define vpii vector<pair<int,int>>
  19. #define mii map<int,int>
  20. #define si set<int>
  21. #define input(v,n) for(int i = 0 ; i< n ; i++) cin >> v[i]
  22. #define output(v)  for(auto it : v) cout << it << endl;
  23. #define IS_POWER_OF_TWO(n) ((n) && !((n) & ((n) - 1)))
  24. #define bug(...) _f (#__VA_ARGS__,__VA_ARGS__)
  25.  
  26. #define lb(x,w,z) for(int x=w;x<z;x++)
  27. #define FOR (x,y) for(auto x:y)
  28. #define revlop(a,b,c) for(int a=b;a>=c;a--)
  29.  
  30. // #include <ext/pb_ds/assoc_container.hpp>
  31. // #include <ext/pb_ds/tree_policy.hpp>
  32. // using namespace std;
  33. // using namespace __gnu_pbds;
  34. // template<class t> using ordered_multiset = tree<t, null_type, less<t>, rb_tree_tag, tree_order_statistics_node_update>;
  35. //---------------------------------------------------------------
  36.  
  37. int dx[] = {0, 0, -1, 1, -1, -1, 1, 1};
  38. int dy[] = {1, -1, 0, 0, 1, -1, 1, -1};
  39.  
  40. using namespace std;
  41. void fast() {
  42.     ios_base::sync_with_stdio(false);
  43.     cin.tie(NULL);
  44.     cout.tie(NULL);
  45. }
  46.  
  47. // const ll  N= 2e6+5;
  48. // ll  pre[N],pre2[N],next_arr[N],arr[N],bb[N] ;
  49. /*
  50.  
  51. ll sqrtt(ll n){
  52. ll l{},r= 1000000000+1,mid;
  53. while(r-l>1){
  54.     mid = l+(r-l)/2;
  55.     if( mid * mid > n )r=mid;
  56.     else l =mid;
  57. }
  58. return l;
  59. }
  60.  
  61. ll lcm ( ll a , ll b)
  62. {
  63.     return (a*b)/gcd(a,b);
  64. }
  65.  
  66. ll fast_power(ll a,ll b , int mod){
  67.     ll ans=1;
  68.     while(b){
  69.     if(b&1){
  70.         ans*=a;
  71.         ans%=mod;
  72.     }
  73.     a*=a;
  74.     a%=mod;
  75.     b = (b>>1);
  76. }
  77. return ans;
  78. }
  79. /*
  80. ll gcd ( ll a, ll b)
  81. {
  82.     if ( b == 0 )
  83.         return a;
  84.     return gcd(b, a%b);
  85. }
  86. vector<int> vis(N);
  87. vector<int> prime(N ) ;
  88. void get_prime(){
  89.     prime[0] = 0 , prime[1] = 1 ;
  90.     for (int i = 2 ; i<= N ; i++){
  91.         if ( !prime[i]  ){
  92.             for (int j = i ; j <= N ; j+=i)
  93.                 prime[j] = i ;
  94.  
  95.         }
  96.     }
  97. }
  98.  
  99. vi prims(N);
  100. void seive(int n ){
  101.     prims[0] = prims[1] = 1;
  102.     for (int  i = 2 ; i* i <= n ; i++){
  103.         if ( !prims[i] ){
  104.             prims[i]  = 0 ;
  105.             for (int j = 2*i ; j <= n ; j+=i ){
  106.                 prims[j] = 1;
  107.             }
  108.         }
  109.     }
  110. }
  111.  
  112. vector<int> prim_fac(ll n ){
  113.     vector<int> v;
  114.     for (int i = 2 ; i*i <= n ;i ++ ){
  115.         while (n != 1 ){
  116.             if ( n % i == 0 ){
  117.                 n/=i;
  118.                 v.push_back(i);
  119.             }
  120.             else break;
  121.         }
  122.     }
  123.     return v;
  124. }
  125.  
  126. bool is_prime(int n)
  127. {
  128.     bool isprime = true;
  129.     if ( n == 1)
  130.         return false;
  131.     for (int i = 2 ; i * i <= n ; i++)
  132.     {
  133.         if ( n %i == 0 )
  134.             isprime = false;
  135.     }
  136.     return isprime;
  137. }*/
  138.  
  139.  
  140.  
  141. const  ll oo = 1e18+2 , mod = 1e9+7 ;
  142. const  int N = 1e5+5;
  143.  
  144.  
  145.  
  146.  
  147. vector<pair<int,int>> adj[N] ;
  148. vector<int> dist(N, oo) , ans , path(N) , mn (N) , mx(N) ;
  149.  
  150. map<int,int> mp;
  151.  
  152. map<int, vector<int>> flights;
  153.  
  154. int n , m , k ;
  155.  
  156. void dijkstra( int src ) { 
  157.     priority_queue< pii , vector<pii> , greater<>> pq;
  158.     pq.push({ 0, src});
  159.     dist[src] = 0 ;
  160.     mn[1] = 0 , mx [1 ] = 0 , path[1] = 1 ;
  161.     while ( !pq.empty()){
  162.         int curr = pq.top().second;
  163.         int d = pq.top().first;
  164.         pq.pop();
  165.         if ( dist[curr] != d){
  166.             continue;
  167.         }
  168.         for (auto it : adj[curr]){
  169.             if ( dist[it.first] > it.second + d ){
  170.                 dist[it.first] = it.second + d ;
  171.                 pq.push({dist[it.first] , it.first});
  172.                 path[it.first] = path[curr];
  173.                 mn[it.first] = mn[curr]+1;
  174.                 mx[it.first] = mx[curr] + 1 ;
  175.             }
  176.             else if ( dist[it.first] == it.second + d ){
  177.                 path[it.first] = ( path[it.first] % mod + path[curr]%mod  ) % mod ;
  178.                 mn[it.first] = min ( mn[it.first] , mn[curr] +1 );
  179.                 mx[it.first] = max ( mx[it.first] , mx[curr] +1 );
  180.             }
  181.         }
  182.     }
  183.  
  184. }
  185.  
  186.  
  187. void solve( ){
  188.     cin >> n >> m  ;
  189.     while ( m -- ){
  190.         int a , b , w ;
  191.         cin >> a  >>  b >> w ;
  192.         adj[a].push_back({b,w });
  193.     }
  194.     dijkstra(1);
  195.     cout << dist[n] << ' ' << path[n] << ' ' << mn[n] <<' '<< mx[n] << endl;
  196.  
  197.  
  198. }
  199.  
  200. signed main( )
  201. {
  202.     //   freopen("input.txt","r",stdin);
  203.     //  freopen("output.txt","w",stdout);
  204. //#endif
  205.     fast();
  206.     int t =1;
  207.     clock_t w =clock();
  208.     // cin >> t ;
  209.     while ( t -- ){
  210.         solve();
  211.     }
  212.  
  213. // cerr << "Run time : " << ((double) (clock() - w) / CLOCKS_PER_SEC);
  214. }
  215.  
Success #stdin #stdout 0.01s 8592KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1000000000000000000 0 0 0
https://ideone.com/I31fjK
language:
C++ (gcc 8.3)
created:
16 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!