Advertisement
Josif_tepe

Untitled

Sep 27th, 2021
163
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.65 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. #include <algorithm>
  5. using namespace std ;
  6. struct  node{
  7.     int index,najmal_pat,money;
  8.  
  9.     node(int i,int p,int m){
  10.         index = i;
  11.         najmal_pat = p;
  12.             money = m;
  13.     }
  14.     bool  operator < (const node &tmp)const {
  15.         return najmal_pat > tmp.najmal_pat;
  16.     }
  17. };
  18. int dist[3005][2005];
  19. int main() {
  20. int S, N , M;
  21. cin >> S >> N >> M;
  22. vector<node> graph[N+5];
  23.     for (int i = 0; i < M; i++) {
  24.         int v,w,t,e;
  25.         cin >> v >> w >> t >> e;
  26.         graph[v].push_back(node(w,t,e));
  27.         graph[w].push_back(node(v,t,e));
  28.     }
  29.     priority_queue<node> pq;
  30.     pq.push(node(1,0,0));
  31.     for (int i = 0; i < 3005; i++) {
  32.         for (int j = 0; j < 2005; j++) {
  33.             dist[i][j] = 2e9;
  34.         }
  35.     }
  36.     dist[1][0] = 0;
  37.     while(!pq.empty()){
  38.         node current = pq.top();
  39.         pq.pop();
  40.  
  41.         for (int i = 0; i < graph[current.index].size(); i++) {
  42.             int sosed = graph[current.index][i].index;
  43.             int pat = graph[current.index][i].najmal_pat;
  44.             int pari = graph[current.index][i].money;
  45.  
  46.             if(pari+current.money <= S && current.najmal_pat + pat < dist[sosed][pari+current.money]){
  47.                 dist[sosed][pari + current.money] = current.najmal_pat + pat;
  48.                 pq.push(node(sosed,current.najmal_pat +pat,current.money + pari));
  49.             }
  50.         }
  51.     }
  52.     int rezultat= 2e9;
  53.     for (int i = 0; i <= S; i++) {
  54.         rezultat = min(dist[N][i], rezultat);
  55.     }
  56.     if (rezultat == 2e9){
  57.         cout << "-1";
  58.     }
  59.     else
  60.         cout << rezultat << endl;
  61. }
  62.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement