fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std ; 
  3.  
  4.  
  5. #define ll long long 
  6. #define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  7. #define fir first 
  8. #define sec second 
  9. #define piint pair < int , int >
  10. #define FOR( i , a , b ) for (int i = (a) , _b = (b) ; i <= _b ; i ++ )  
  11. #define FORD( i , a , b ) for (int i = (a) , _b = (b) ; i >= _b ; i -- )  
  12.  
  13. #define pb push_back 
  14. #define str string 
  15. #define ALL(a) (a).begin() , (a).end() 
  16. #define rep( i , a , b) for (int i = (a) ; i < (b) ; i ++ )
  17. #define ld long double
  18. const int maxn = 10000 ;
  19. #define debug 0
  20. #define oo (ll)(1e18)
  21.  
  22. std::vector< pair < int , ll > > G[maxn +3 ];
  23. vector < int > bfs[maxn + 3] ;
  24.  
  25. bool spoill[maxn + 3 ] ;
  26. ll ans = oo ;
  27. struct T {
  28.     ll du ;
  29.     int u , Count ; 
  30. } ;
  31. struct cmp 
  32. {
  33.     bool operator() ( T a , T b ) {
  34.         return a.du > b.du ;
  35.     }
  36. } ;
  37. #define skip continue;
  38. int n , m , p , l , k ; 
  39. ll dp[maxn +3 ][13] ;
  40. void dijk ( int st ) {
  41.     FOR ( i , 1 , n ) {
  42.         FOR ( j , 0 , k ) dp[i][j] = oo ;
  43.     }
  44.     dp[st][0] = 0 ;
  45.     priority_queue < T , vector <T> , cmp > q ;
  46.     q.push ( { 0 , st , 0 }) ;
  47.     while (q.size()){
  48.         auto [ du , u , Count ] = q.top() ;
  49.         if ( u == n ) ans = min ( ans , du ) ; //, cout << du << '\n' ;
  50.         q.pop() ;
  51.         if ( du > dp[u][Count] ) skip 
  52.         for (auto [ v , w ] : G[u]){
  53.             ll new_dp = du + w ;
  54.             if ( dp[v][Count] > new_dp ){
  55.                 dp[v][Count] = new_dp ;
  56.                 q.push ( { new_dp , v , Count }) ;
  57.             }
  58.         }
  59.         if ( Count < k ) {
  60.             for (auto v : bfs[u]){
  61.                  ll new_dp = du + p ;
  62.                  int N_Count = Count + 1 ;
  63.                  if ( dp[v][N_Count] > new_dp ){
  64.                     dp[v][N_Count] = new_dp ;
  65.                     q.push ( { new_dp , v , N_Count }) ;
  66.                 }
  67.             }
  68.         }
  69.     }
  70. }
  71. void input(){
  72.     cin >> n >> m >> p >> l >> k ;
  73.     FOR ( i , 1 , m ) {
  74.         int u , v , w ; cin >> u >> v >> w ; 
  75.         G[u].pb ( { v , w }) ;
  76.         G[v].pb ( { u , w }) ;
  77.     }
  78.     FOR ( i , 1 , n ) {
  79.         fill ( spoill + 1 , spoill + n + 1 , 0 ) ; 
  80.         queue < piint > q ;
  81.         q.push ( { i , 0 }) ;
  82.         spoill[i] = 1 ;
  83.         while ( q.size() ) {
  84.             auto [ u , du ] = q.front() ;
  85.             q.pop() ;
  86.  
  87.             if ( du == l ) continue ; 
  88.             for (auto [v , w ] : G[u]) {
  89.                 if(!spoill[v]) {
  90.                     spoill[v] = 1 ;
  91.                     bfs[i].pb ( v) ;
  92.                     q.push ( make_pair(v , du + 1) ) ;
  93.                 }
  94.             }
  95.         }
  96.     }
  97.     dijk ( 1 ) ;
  98.     cout << ans ;
  99. }
  100. void solve() {
  101.  
  102. }
  103. #define name "MINPATH" 
  104. int main(){
  105.     fast 
  106.     if(fopen(name".INP","r")) {
  107.         freopen (name".INP","r",stdin);
  108.         freopen (name".OUT","w",stdout);
  109.     }
  110.     input() ;
  111.     solve() ;
  112.     cerr << "\nTIME: = " << (1.0*clock())/CLOCKS_PER_SEC << '\n';
  113.     return(0) ;
  114. }
Success #stdin #stdout #stderr 0.01s 5316KB
comments (?)
stdin 
Standard input is empty
stdout 
1000000000000000000
stderr 
TIME: = 0.004401
https://ideone.com/D3xCFX
language:
C++14 (gcc 8.3)
created:
1 day 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!