fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4. const int maxN = 1e6 + 5;
  5. const int mod = 1e9 + 7;
  6.  
  7. struct Tpq {
  8.     int ver,rmn;
  9.     ll val;
  10. };
  11.  
  12. struct functer {
  13.     bool operator()(Tpq a,Tpq b) {
  14.         return ((a.val > b.val) || (a.val == b.val && make_pair(a.ver,a.rmn) < make_pair(b.ver,b.rmn)));
  15.     }
  16. };
  17.  
  18. int n,m;
  19. ll C[maxN];
  20. int D[maxN];
  21. vector<int> adj[maxN];
  22. ll d[5005][105];
  23.  
  24. int main() {
  25.     ios_base::sync_with_stdio(false);
  26.     cin.tie(0);
  27.     cin >> n >> m;
  28.     for(int i = 1; i <= n; i++) {
  29.         cin >> C[i] >> D[i];
  30.     }
  31.     for(int i = 1; i <= m; i++) {
  32.         int x,y;
  33.         cin >> x >> y;
  34.         adj[x].push_back(y);
  35.         adj[y].push_back(x);
  36.     }
  37.     for(int i = 1; i <= n; i++) {
  38.         for(int j = 0; j <= 100; j++) {
  39.             d[i][j] = 1e18;
  40.         }
  41.     }
  42.     priority_queue<Tpq,vector<Tpq>,functer> pq;
  43.     d[1][D[1]] = C[1];
  44.     pq.push({1,D[1],C[1]});
  45.  
  46.     while(!pq.empty())
  47.     {
  48.         auto[u,rmn,val] = pq.top();
  49.         pq.pop();
  50.         if(d[u][rmn] < val) continue;
  51.         if(u == n) {cout << val;return 0;}
  52.  
  53.         for(int v : adj[u])
  54.         {
  55.             if(rmn > 0)
  56.             {
  57.                 if(val < d[v][rmn-1])
  58.                 {
  59.                     d[v][rmn-1] = val;
  60.                     pq.push({v,rmn-1,val});
  61.                 }
  62.             }
  63.             if(val + C[v] < d[v][D[v]])
  64.             {
  65.                 d[v][D[v]] = val + C[v];
  66.                 pq.push({v,D[v],val+C[v]});
  67.             }
  68.         }
  69.  
  70.     }
  71. }
  72.  
  73.  
Success #stdin #stdout 0.01s 28152KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Ik8Mg4
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!