Advertisement
Josif_tepe

Untitled

Oct 12th, 2021
124
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.52 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. using namespace  std;
  5. struct node {
  6.     int index,najmal_pat;
  7.  
  8.     node(int s,int p){
  9.         index = s;
  10.         najmal_pat = p;
  11.     }
  12.     bool operator  < (const node&tmp) const {
  13.         return najmal_pat > tmp.najmal_pat;
  14.     }
  15. };
  16. int main() {
  17.     int n,v;
  18.     cin >> n >> v;
  19.     vector<int> graph[15];
  20.     int niza[n];
  21.     for (int i = 0; i < n; i++) {
  22.         cin >> niza[i];
  23.         graph[niza[i]].push_back(i);
  24.     }
  25.  
  26.     priority_queue<node> pq;
  27.     vector<bool> visited (n+1, false);
  28.     vector<bool> portali(15, false);
  29.     pq.push(node(0,0));
  30.     while(!pq.empty()){
  31.         node current = pq.top();
  32.         pq.pop();
  33.  
  34.         visited[current.index] = true;
  35.         if(current.index == n-1){
  36.             cout << current.najmal_pat;
  37.             break;
  38.         }
  39.         if(!portali[niza[current.index]]) {
  40.             for (int i = 0; i < graph[niza[current.index]].size(); i++) {
  41.                 int sosed = graph[niza[current.index]][i];
  42.                 int pat = current.najmal_pat + v;
  43.                 if(!visited[sosed])
  44.                     pq.push(node(sosed, pat));
  45.             }
  46.             portali[niza[current.index]] = true;
  47.         }
  48.  
  49.         if(current.index > 0 and !visited[current.index - 1]){
  50.             pq.push(node(current.index -1,current.najmal_pat +1));
  51.  
  52.         }
  53.         if(current.index < n and !visited[current.index + 1]){
  54.             pq.push(node(current.index +1,current.najmal_pat+1));
  55.         }
  56.     }
  57.  
  58. }
  59.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement