Advertisement
Josif_tepe

Untitled

May 22nd, 2021
130
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.61 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. using namespace std;
  5. struct node{
  6. int distance;
  7. int cena;
  8. int index;
  9.  
  10. node(){
  11.  
  12.  
  13. }
  14.  
  15. node(int _index, int _distance, int _cena){
  16. index=_index;
  17. distance=_distance;
  18. cena=_cena;
  19. }
  20.  
  21. bool operator <(const node&tmp)const{
  22. return distance > tmp.distance;
  23. }
  24.  
  25.  
  26.  
  27.  
  28.  
  29. };
  30. int main()
  31. {
  32.     int n;
  33.     int m;
  34.     int S;
  35.     int S1=200000000;
  36.  
  37.  
  38.     cin>>S;
  39.     cin>>n>>m;
  40.     int matrica[n+1][S + 1];
  41.     vector<node>v[n+1];
  42.  
  43.     for(int x1=0; x1<n+1; x1++){
  44.         for(int s1=0; s1<= S; s1++){
  45.             matrica[x1][s1]=2000000000;
  46.         }
  47.  
  48.     }
  49.     for(int x=0; x<m; x++){
  50.     int indexa;
  51.     int indexb;
  52.     int distance;
  53.     int cost;
  54.     cin>>indexa>>indexb>>distance>>cost;
  55.     v[indexa].push_back(node(indexb, distance, cost));
  56.     v[indexb].push_back(node(indexa, distance, cost));
  57.     }
  58.     priority_queue<node>pq;
  59.     pq.push(node(1, 0, 0));
  60.  
  61.     matrica[1][0]=0;
  62.  
  63.     while(!pq.empty()){
  64.     node cnode=pq.top();
  65.     pq.pop();
  66.     for(int h=0; h<v[cnode.index].size(); h++){
  67.     int  sosed=v[cnode.index][h].index;
  68.     int distance=v[cnode.index][h].distance;
  69.     int cena=v[cnode.index][h].cena;
  70.     if((cena+cnode.cena<=S)and(matrica[sosed][cena+cnode.cena]>distance+cnode.distance)){
  71.     matrica[sosed][cena+cnode.cena]=distance+cnode.distance;
  72.     pq.push(node(sosed, distance+cnode.distance, cena+cnode.cena));
  73.     }
  74.     }
  75.  
  76.  
  77.     }
  78.      for(int y=0; y<=S; y++){
  79.      if(matrica[n][y]<S1){
  80.      S1=matrica[n][y];
  81.      }
  82.      }
  83.     if(S1 == 200000000) {
  84.         S1 = -1;
  85.     }
  86.     cout<<S1;
  87.     return 0;
  88. }
  89.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement