1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

#include <iostream>
#include <vector>
#include <queue>
#include <numeric>
#include <algorithm>

class Solution {
public:
    int findMaxPathScore(std::vector<std::vector<int>>& edges, std::vector<bool>& online, long long k) {
        int n = online.size();
        if (n == 1) {
            return 0;
        }
        
        int left = 0x7fff'ffff, right = 0, res = -1;
        std::vector<std::vector<std::pair<int, long long>>> adj(n);
        std::vector<long long> dist(n);
        
        for (auto& e : edges) {
            if (!online[e[0]] || !online[e[1]]) {
                continue;
            }
            left = std::min(left, e[2]);
            right = std::max(right, e[2]);
            adj[e[0]].push_back({e[1], e[2]});
        }
        if (left == 0x7fff'ffff && right == 0) {
            return -1;
        }
        
        while (right >= left) {
            int mid = (left + right) / 2;
            bool valid = false;
            std::priority_queue<std::pair<long long, int>, std::vector<std::pair<long long, int>>, std::greater<std::pair<long long, int>>> pq;
            
            std::fill(dist.begin(), dist.end(), 0x7fff'ffff'ffff'ffff);
            dist[0] = 0;
            
            pq.push({0, 0});
            
            while (!pq.empty()) {
                long long d = pq.top().first;
                int u = pq.top().second;
                if (u == n - 1) {
                    valid = true;
                    break;
                }
                pq.pop();
                if (d > dist[u]) {
                    continue;
                }
                for (auto& e : adj[u]) {
                    if (e.second < mid) {
                        continue;
                    }
                    long long nd = d + e.second;
                    if (nd > k || nd >= dist[e.first]) {
                        continue;
                    }
                    pq.push({nd, e.first});
                    dist[e.first] = nd;
                }
            }
            
            if (valid) {
                res = mid;
                left = mid + 1;
            }
            else {
                right = mid - 1;
            }
        }
        
        return res;
    }
};