Advertisement
Josif_tepe

Untitled

May 19th, 2021
144
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.34 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. using namespace std;
  5.  
  6. struct node{
  7. int index;
  8. int cost;
  9. int snow;
  10. node(){
  11.  
  12. }
  13. node( int _index, int _cost, int _snow){
  14. index=_index;
  15. cost=_cost;
  16. snow=_snow;
  17. }
  18. bool operator < (const node&tmp) const{
  19. return cost>tmp.cost;
  20.  
  21. }
  22.  
  23.  
  24. };
  25. int main()
  26. {
  27.     int N;
  28.     int M;
  29.     cin>>N>>M;
  30.     vector<node> v[N + 1];
  31.     for(int x=0; x<M; x++){
  32.         int a;
  33.         int b;
  34.         int c;
  35.         int d;
  36.         cin>>a>>b>>c>>d;
  37.         v[a].push_back(node(b, c, d));
  38.         v[b].push_back(node(a, c, d));
  39.     }
  40.     priority_queue<node>pq;
  41.     pq.push(node(1, 0, 1));
  42.     bool matrica[N + 1];
  43.     for(int x1=0; x1 <= N; x1++){
  44.         matrica[x1]=false;
  45.     }
  46.     while(!pq.empty()){
  47.     node c=pq.top();
  48.     pq.pop();
  49.     matrica[c.index]=true;
  50.  
  51.     if(c.index==N){
  52.     cout<<c.cost<<endl;
  53.     if(c.snow==1){
  54.     cout<<"DA";
  55.     }
  56.     else{
  57.     cout<<"NE";
  58.     }
  59.     return 0;
  60.     }
  61.  
  62.     for(int i=0; i<v[c.index].size(); i++){
  63.     int sosed=v[c.index][i].index;
  64.     int snow1=v[c.index][i].snow;
  65.     int pat=v[c.index][i].cost;
  66.  
  67.     if((c.snow==1)and(snow1==1)and(matrica[sosed]==false)){
  68.     pq.push(node(sosed, pat+c.cost, 1));
  69.     }
  70.  
  71.     else if(matrica[sosed]==false){
  72.     pq.push(node(sosed, pat+c.cost, 0));
  73.     }
  74.     }
  75.     }
  76.     return 0;
  77. }
  78.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement