leetcode 743. Network Delay Time 网络延迟时间

Problem: 743. Network Delay Time 网络延迟时间

解题过程

堆优化迪杰特斯拉版本，Dijkstra方案，找到k到其他每个node的最短时间，然后求出所有node的最大时间，最大值(每个node的最小时间)

深度优先或者广度优先都可以做，但是环太多了

Code

using pr = pair<int, int>; class Solution { public: // int mx = INT_MIN; int dis[101], start, nn; unordered_map<int, int> ump; void dfs(vector<vector<pair<int, int>>>& tr, int k, int cnt, int pre) { // mx = max(mx, cnt); // status[k] = true; dis[k] = min(dis[k], cnt); int key = (k * 10000) + pre; if( ump.find(key) != ump.end() && ump[key] >= 300*nn) { return; } ump[key]++; if(k==4) { int ww = 0; } for(int i = 0; i < tr[k].size(); i++) { // if(status[tr[k][i].first]==false) { if(tr[k][i].first == start) continue; dfs(tr, tr[k][i].first, cnt + tr[k][i].second, k); // } } } int networkDelayTime(vector<vector<int>>& times, int n, int k) { vector<vector<pair<int, int>>> tr(n+1); nn = n; for(int i = 0; i < times.size(); i++) { tr[times[i][0]].push_back({times[i][1], times[i][2]}); } // for(int i = 1; i <= n; i++) { // sort(tr[i].begin(), tr[i].end(), [](pair<int, int>& a, pair<int, int>&c) { // return a.second < c.second; // }); // } vector<int> disdis(n+1, INT_MAX); vector<bool> status(n+1, false); disdis[k] = 0; priority_queue<pr, vector<pr>, greater<pr>> pq; pq.push({0, k}); int dest, distance, next, nextD; while(!pq.empty()) { pr pai = pq.top(); distance = pai.first; dest = pai.second; pq.pop(); if(status[dest]) continue; status[dest] = true; for(int i = 0; i < tr[dest].size(); i++) { next = tr[dest][i].first; nextD = tr[dest][i].second; if(status[next]==false && disdis[next] > distance + nextD) { disdis[next] = distance + nextD; pq.push({disdis[next], next}); } } } // start = k; // fill(dis, dis+101, INT_MAX); // dfs(tr, k, 0, -1); int mx = INT_MIN; for(int i = 1; i <= n; i++) { mx = max(disdis[i], mx); } if(mx==INT_MAX) return -1; return mx; // vector<bool> status(n+1, false); // queue<pair<int,int>> qe; // qe.push({k, 0}); // int mimi = INT_MAX; // while(!qe.empty()) { // int sz = qe.size(); // int mx = INT_MIN; // for(int i = 0; i < sz; i++) { // int ll = qe.front().first; // int d = qe.front().second; // mx = max(d, mx); // status[ll] = true; // for(int j = 0; j < tr[ll].size(); j++) { // // if(status[tr[ll][j].first]==false) { // qe.push({tr[ll][j].first, tr[ll][j].second + d}); // // } // } // qe.pop(); // } // bool ret = true; // for(int i = 1; i < status.size(); i++) { // if(status[i]==false) { // ret = false; // break; // } // } // if(ret) { // mimi = min(mimi, mx); // } // } // for(int i = 1; i < status.size(); i++) { // if(status[i]==false) return -1; // } // return mimi; } };