最短路径-Dijkstra及其堆优化版本

743. 网络延迟时间 - 力扣（LeetCode）

朴素版本：O n2复杂度，邻接矩阵建图

class Solution {
public:int networkDelayTime(vector<vector<int>>& times, int n, int k) {vector<int>vis(n,0),dist(n,INT_MAX/2);vector<vector<int>>graph(n,vector<int>(n,INT_MAX/2));for(int i=0;i<times.size();i++)graph[times[i][0]-1][times[i][1]-1]=times[i][2];dist[k-1]=0;for(int i=0;i<n;i++){int x=-1;for(int y=0;y<n;y++)if(!vis[y]&&(x==-1||dist[y]<dist[x]))x=y;vis[x]=1;for(int y=0;y<n;y++)dist[y]=min(dist[y],dist[x]+graph[x][y]);}int res=-1;for(int i=0;i<n;i++)res=max(res,dist[i]);return res==INT_MAX/2?-1:res;}
};

堆优化：O(mlogm)，邻接表建图

class Solution {
public:int networkDelayTime(vector<vector<int>>& times, int n, int k) {vector<vector<pair<int, int>>> g(n); // 邻接表for (auto& t : times) {g[t[0] - 1].emplace_back(t[1] - 1, t[2]);}vector<int> dis(n, INT_MAX);dis[k - 1] = 0;priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;pq.emplace(0, k - 1);while (!pq.empty()) {auto [dx, x] = pq.top();pq.pop();if (dx > dis[x]) { // x 之前出堆过continue;}for (auto &[y, d] : g[x]) {int new_dis = dx + d;if (new_dis < dis[y]) {dis[y] = new_dis; // 更新 x 的邻居的最短路pq.emplace(new_dis, y);}}}int mx = ranges::max(dis);return mx < INT_MAX ? mx : -1;}
};