\u5229\u7528C++\u5b9e\u73b0\u4e86Dijkstra\u7b97\u6cd5.<\/p>\n
<\/p>\n
\u9898\u76ee\u6765\u81eaLeetCode 743.Network Delay Time.<\/p>\n
\r\nclass Solution {\r\npublic:\r\n int networkDelayTime(vector<vector<int>>& times, int N, int K) {\r\n if(times.empty()) return -1;\r\n priority_queue<pair<int,int>,vector<pair<int,int>>,compare> pq;\r\n unordered_map<int,vector<vector<int>>> hash;\r\n for(auto time:times)\r\n {\r\n if(hash.find(time[0])!=hash.end())\r\n {\r\n vector<vector<int>> temp=hash[time[0]];\r\n temp.push_back({time[1],time[2]});\r\n hash[time[0]]=temp;\r\n }\r\n else\r\n hash[time[0]]={{time[1],time[2]}};\r\n }\r\n vector<int> distance(N+1,INT_MAX);\r\n distance[K]=0;\r\n pq.push({K,0});\r\n while(!pq.empty())\r\n {\r\n int u=pq.top().first;\r\n pq.pop();\r\n if(hash.find(u)!=hash.end())\r\n {\r\n vector<vector<int>> Adjs=hash[u];\r\n for(auto adj:Adjs)\r\n {\r\n int v=adj[0];\r\n int w=adj[1];\r\n if(distance[v]>distance[u]+w)\r\n {\r\n distance[v]=distance[u]+w;\r\n pq.push({v,distance[v]});\r\n }\r\n }\r\n }\r\n }\r\n int result=0;\r\n for(int i=1;i<=N;i++)\r\n {\r\n if(distance[i]==INT_MAX) return -1;\r\n result=max(result,distance[i]);\r\n }\r\n return result;\r\n }\r\n \r\n struct compare{\r\n bool operator()(const pair<int,int>& a,const pair<int,int>& b){\r\n return a.second>b.second;\r\n }\r\n };\r\n};\r\n<\/pre>\n\u65f6\u95f4\u590d\u6742\u5ea6\u5927\u81f4\u4e3aO(vlogv), \u5176\u4e2dv\u4e3a\u56fe\u9876\u70b9\u7684\u6570\u76ee. \u4e5f\u53ef\u4ee5\u5c06\u56fe\u7528\u4e00\u4e2a\u4e8c\u7ef4vector\u53bb\u5b58\u50a8\u800c\u975e\u7528Hash Table, \u8fd9\u6837\u901f\u5ea6\u80fd\u5feb\u4e0a10\u500d\u5de6\u53f3, \u867d\u7136\u727a\u7272\u4e86\u4e00\u70b9\u7a7a\u95f4\u2026\u2026<\/p>\n
\r\nstruct cmp {\r\n bool operator()(const pair<int, int>& left, const pair<int, int>& right) \r\n { \r\n return left.second > right.second; \r\n } \r\n};\r\n\r\nclass Solution {\r\npublic:\r\n\r\n std::vector<int> distances;\r\n std::vector<vector<pair<int, int>>> edgeList;\r\n std::priority_queue<pair<int, int>, vector<pair<int,int>>, cmp> paths;\r\n std::vector<bool> completed;\r\n \r\n int networkDelayTime(vector<vector<int>>& times, int N, int K) {\r\n \r\n distances = vector<int>(N, -1);\r\n distances[K-1] = 0;\r\n completed = vector<bool>(N, false);\r\n edgeList = vector<vector<pair<int, int>>> (N);\r\n \r\n for(auto n: times) { \/\/ Make adjacency list\r\n edgeList[n[0]-1].push_back(make_pair(n[1], n[2]));\r\n }\r\n \r\n paths.push(make_pair(K, 0));\r\n \r\n int time = 0, curNode = 0, nextTime = 0;\r\n \r\n while(!paths.empty()) {\r\n \r\n auto fastestNode = paths.top(); \/\/ Get node with lowest time \r\n paths.pop();\r\n \r\n curNode = fastestNode.first;\r\n time = fastestNode.second;\r\n \r\n if(completed[curNode-1]) continue; \/\/ Stop if node is already completed\r\n \r\n completed[curNode-1] = true; \/\/ Mark node as completed\r\n \r\n for(auto n: edgeList[curNode-1]) { \/\/ Add edges of this node that has better time as possible paths\r\n nextTime = time + n.second;\r\n if(distances[n.first-1] == -1 || nextTime < distances[n.first-1]){\r\n distances[n.first-1] = nextTime;\r\n paths.push(make_pair(n.first, nextTime));\r\n }\r\n }\r\n }\r\n \r\n int best = 0;\r\n for(auto n: distances) { \/\/ Find the max distances, which would be time it takes to reach all nodes\r\n if(n == -1) {return -1;} \/\/ If a node is not reached from starting node\r\n if(best < n) best = n;\r\n }\r\n \r\n return best;\r\n }\r\n};\r\n\r\nauto gucciGang = []() {std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"\u5229\u7528C++\u5b9e\u73b0\u4e86Dijkstra\u7b97\u6cd5.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[5],"tags":[],"_links":{"self":[{"href":"https:\/\/www.caiqinyi.cn\/index.php\/wp-json\/wp\/v2\/posts\/179"}],"collection":[{"href":"https:\/\/www.caiqinyi.cn\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.caiqinyi.cn\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.caiqinyi.cn\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.caiqinyi.cn\/index.php\/wp-json\/wp\/v2\/comments?post=179"}],"version-history":[{"count":10,"href":"https:\/\/www.caiqinyi.cn\/index.php\/wp-json\/wp\/v2\/posts\/179\/revisions"}],"predecessor-version":[{"id":182,"href":"https:\/\/www.caiqinyi.cn\/index.php\/wp-json\/wp\/v2\/posts\/179\/revisions\/182"}],"wp:attachment":[{"href":"https:\/\/www.caiqinyi.cn\/index.php\/wp-json\/wp\/v2\/media?parent=179"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.caiqinyi.cn\/index.php\/wp-json\/wp\/v2\/categories?post=179"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.caiqinyi.cn\/index.php\/wp-json\/wp\/v2\/tags?post=179"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}