单源最短路径,其实就是求某个节点到其他所有节点中路径的最大值
class Solution { public: void dijkstra(vector<vector<int>>& w, int k, int n,vector<bool>& vis,vector<int>& dist) { // 只有起点k最短距离为 0 dist[k] = 0; // 迭代 n 次, n表示一共n个节点 for (int p = 1; p <= n; p++) { // 每次找到「最短距离最小」且「未被更新」的点 t int t = -1; for (int i = 1; i <= n; i++) { if (!vis[i] && (t == -1 || dist[i] < dist[t])) t = i; } // 标记点 t 为已更新 vis[t] = true; // 用点 t 的「最小距离」更新其他点 for (int i = 1; i <= n; i++) { dist[i] = min(dist[i], dist[t] + w[t][i]); // cout<<i<<":" <<dist[i]<<endl; } } } int networkDelayTime(vector<vector<int>>& times, int n, int k) { // 数组的长度根据题目每个参数的最大值进行设定 vector<vector<int>> w(101,vector<int>(101)); int INF = 0x3f3f3f3f; // 起始先将所有的点标记为「未更新」和「距离为正无穷」 expected parameter declarator vector<bool> vis = vector<bool>(101, false); vector<int> dist = vector<int>(101, INF); // 初始化邻接矩阵 for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { w[i][j] = w[j][i] = i == j ? 0 : INF; } } // 存图 for (auto t : times) { int u = t[0], v = t[1], c = t[2]; // cout<<"val:" <<u<<" "<<v<<" "<<c<<endl; w[u][v] = c; } dijkstra(w,k,n,vis,dist); int res = 0; for(int i = 1; i <= n; i++){ res = max(res, dist[i]); } return res > INF / 2 ? -1 : res; } };