Advertisement
Josif_tepe

Untitled

Feb 20th, 2024
658
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.07 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <queue>
  4. #include <vector>
  5. using namespace std;
  6. const int maxn = 1e5 + 10;
  7. int n, m, k;
  8. int gas[maxn];
  9. vector<int> graph[maxn];
  10. struct node {
  11.     int idx, passed, mood;
  12.     node () {}
  13.     node(int _idx, int _passed, int _mood) {
  14.         idx = _idx;
  15.         passed = _passed;
  16.         mood = _mood;
  17.     }
  18.    
  19.     bool operator < (const node & tmp) const {
  20.         int score1 = 0, score2 = 0;
  21.         if(mood > tmp.mood) {
  22.             score1++;
  23.         }
  24.         else {
  25.             score2++;
  26.         }
  27.         if(passed < tmp.passed) {
  28.             score1++;
  29.         }
  30.         else {
  31.             score2++;
  32.         }
  33.         return score1 < score2;
  34.     }
  35. };
  36.  
  37. int main() {
  38.     ios_base::sync_with_stdio(false);
  39.     cin >> n >> m >> k;
  40.    
  41.     for(int i = 0; i < n; i++) {
  42.         cin >> gas[i];
  43.     }
  44.    
  45.     for(int i = 0; i < m; i++) {
  46.         int a, b;
  47.         cin >> a >> b;
  48.         a--; b--;
  49.         graph[a].push_back(b);
  50.         graph[b].push_back(a);
  51.     }
  52.     priority_queue<node> pq;
  53.     pq.push(node(0, 1, gas[0]));
  54.     vector<int> current_mood(n + 1, -2e9);
  55.     int max_mood = -2e9, min_passing = 2e9;
  56.     while(!pq.empty()) {
  57.         node c = pq.top();
  58.         pq.pop();
  59.        
  60.         if(c.idx == n - 1) {
  61.             if(c.mood > max_mood) {
  62.                 max_mood = c.mood;
  63.                 min_passing = c.passed;
  64.             }
  65.             else if(c.mood == max_mood) {
  66.                 if(min_passing > c.passed) {
  67.                     min_passing = c.passed;
  68.                 }
  69.             }
  70.             continue;
  71.         }
  72.         for(int i = 0; i < (int) graph[c.idx].size(); i++) {
  73.             int neighbour = graph[c.idx][i];
  74.             if(c.passed < k and current_mood[neighbour] < min(c.mood, gas[neighbour])) {
  75.                 pq.push(node(neighbour, c.passed + 1, min(c.mood, gas[neighbour])));
  76.                 current_mood[neighbour] = min(c.mood, gas[neighbour]);
  77.             }
  78.         }
  79.     }
  80.     cout << max_mood << " " << min_passing << endl;
  81.     return 0;
  82. }
  83.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement