Re: [閒聊] 每日leetcode
看板Marginalman作者enmeitiryous (enmeitiryous)時間1年前 (2024/07/26 15:06)推噓2(2推 0噓 1→)留言3則, 3人參與討論串568/1553 (看更多)
題目:給你一個數字n代表有0-n-1座城市，以及二維array edges，edges[i]有三個
數字[a,b,c]代表從a城市到b城市距離為c，這樣的道路是雙向的，最後有一個數字
threshold代表題目希望的基準線，回傳能夠在threshold距離下能拜訪最少城市的城市
編號，如果有複數個城市能拜訪最少城市則回傳編號大的(例如0,1,2,3四個城市分別
在標準下能拜訪2,3,3,2座其他城市則應該要回傳3號城市)
思路:
all pair shortest path problem，可以使用floyd warshall或是對每一個點做
dijkstra(因為沒有負權重邊)，得出全部的shortest path後依照threshold紀錄可拜
訪的城市數，最後依照要求回傳編號，從結果看對全部點做dijkstra可能比較快?
floyd warshall複雜度為O(n^3) n是node數
int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {
//unordered_map<vector<int>,int> weight_list;
vector<vector<int>> gr_ap(n,vector<int> (n,10001));
int ww=edges.size();
for(int i=0;i<ww;++i){
gr_ap[edges[i][0]][edges[i][1]]=edges[i][2];
gr_ap[edges[i][1]][edges[i][0]]=edges[i][2];
}
for(int i=0;i<n;++i){
for(int j=0;j<n;++j){
for(int y=0;y<n;y++){
if(gr_ap[j][y]>gr_ap[j][i]+gr_ap[i][y] && gr_ap[j][i]!=10001
&&gr_ap[i][y]!=10001){
gr_ap[j][y]=gr_ap[j][i]+gr_ap[i][y];
}
}
}
}
vector<int> pre_ans(n,0);
for(int i=0;i<n;++i){
for(int l=0;l<n;++l){
if(gr_ap[i][l]<=distanceThreshold && i!=l){
pre_ans[i]++;
}
}
}
vector<int> ans={0,pre_ans[0]};
for(int i=0;i<n;++i){
if(pre_ans[i]<=ans[1] && i>=ans[0]){
ans={i,pre_ans[i]};
}
}
return ans[0];
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.227.192.85 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1721977586.A.69C.html
推
07/26 15:12,
1年前
, 1F
07/26 15:12, 1F
→
07/26 15:18,
1年前
, 2F
07/26 15:18, 2F
推
07/26 15:30,
1年前
, 3F
07/26 15:30, 3F
討論串 (同標題文章)
完整討論串 (本文為第 568 之 1553 篇)：