Advertisement
Josif_tepe

Untitled

May 27th, 2021
104
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.81 KB | None | 0 0
  1. #include <iostream>
  2. #include<vector>
  3. #include<queue>
  4. using namespace std;
  5. struct node
  6. {
  7.     int idx;
  8.     int distance;
  9.     int money;
  10.     node(){}
  11.     node(int _idx, int _distance, int _money)
  12.     {
  13.         idx=_idx;
  14.         distance=_distance;
  15.         money=_money;
  16.     }
  17.     bool operator < (const node &tmp) const{
  18.         return distance > tmp.distance;
  19.     }
  20. };
  21. int main()
  22. {
  23.     int s;
  24.     int n,m;
  25.     cin>>s>>n>>m;
  26.     vector<node>v[n+1];
  27.     for(int i=0; i<m;i++)
  28.     {
  29.         int a,b,c,d;
  30.         cin>>a>>b>>c>>d;
  31.         v[a].push_back(node(b,c,d));
  32.         v[b].push_back(node(a,c,d));
  33.  
  34.     }
  35.     int dis[n+1][s+1];
  36.     for(int i=0;i<n+1;i++)
  37.     {
  38.         for(int j=0;j<s+1;j++)
  39.         {
  40.             dis[i][j]=2e9;
  41.         }
  42.     }
  43.     priority_queue<node>pq;
  44.     pq.push(node(1,0,0));
  45.     while(!pq.empty())
  46.     {
  47.         node c=pq.top();
  48.         pq.pop();
  49.  
  50.         for(int i=0;i< v[c.idx].size(); i++)
  51.         {
  52.             int sosed = v[c.idx][i].idx;
  53.             int d = v[c.idx][i].distance;
  54.                         int pari= v[c.idx][i].money;
  55.                         if(pari+c.money<=s)
  56.                         {
  57.                             if(d+c.distance<dis[sosed][pari+c.money])
  58.                             {
  59.                                 pq.push(node(sosed, d+c.distance,pari+c.money));
  60.                                 dis[sosed][pari+c.money]=d+c.distance;
  61.                             }
  62.                         }
  63.                     }
  64.                 }
  65.                 int rez=2e9;
  66.                 for(int i=0;i<=s;i++)
  67.                 {
  68.                   rez=min(rez,dis[n][i]);
  69.  
  70.                 }
  71.                 if(rez==2e9)
  72.                     cout<<-1;
  73.                 else
  74.                     cout<<rez;
  75.                 return 0;
  76.             }
  77.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement