leetcode743. Network latency (medium, Dijkstra)

Ideas ： Single source shortest path ->dijkstra Templates

class Solution {
    
public:
    using PII = pair<int, int>;
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
    
        
        vector<int> vis(n + 1), dis(n + 1, INT_MAX);
        vector<vector<PII>> bian(n + 1); // The goal is , distance 
        for (auto& a : times) {
    
            bian[a[0]].push_back({
    a[1], a[2]});
        }
        priority_queue<PII, vector<PII>, greater<PII>> pq; // distance -> Nearest destination 
        pq.push({
    0, k});
        int cnt = 0;
        dis[k] = 0;
        while (!pq.empty()) {
    
            auto [_dis, pos] = pq.top();
            pq.pop();
            if (vis[pos]) continue;
            vis[pos] = true;
            cnt++;
            for (auto& tmp : bian[pos]) {
    
                if (_dis + tmp.second < dis[tmp.first]) {
    
                    dis[tmp.first] = _dis + tmp.second;
                    pq.push({
    dis[tmp.first], tmp.first});
                }
            }
        }
        int ans = 0;
        for (int i = 1; i <= n; ++i) {
    
            ans = max(ans, dis[i]);
        }
        return (cnt == n) ? ans : -1;
    }
};