貪心演算法
%已經得到，經度坐標X，維度坐標Y，距離矩陣DG（距離為經緯度平方和開根號）
n=30； %這里是已知有30個點
x = X; %產生一個與經過點數相同的行向量
y = Y;
d=DG; %距離矩陣
best = 1:1:n; %生成一個用來存盤點順序的矩陣
handle = 1:1:n;
best(1) = 1; %默認起點
num = 1;
for a = 1:(n-2) %需要n-2次判斷
handle(:,1)=[]; %上一次最優點的資料裁掉
dis = zeros(1,(n-a)); %用來存剩下各個點的距離
for b = 1:(n-a) %用來獲取剩下各個點的距離
dis(b) = d (num , handle(b));
end
num1 = find( dis == min(dis) ); %得到最優點所在檢索
t = handle(1); %將最優點與最前面的點位置進行交換
handle(1) = handle(num1);
handle(num1) = t;
num = handle(1); %獲取下次進行操作的數
best(a+1) = handle(1); %將最優點存入best陣列
end
best(n) = handle(num1); %補上最后一個點
x(best)
y(best)
plot(x(best),y(best),'-+') ; %用'+'標出點并用實線連接得到最優路徑
grid on
%得到順序，前面維度輸出為ans
[ians,iY]=find(bsxfun(@eq,ans,Y')); %進行比較得到位移順序
w=accumarray(iY,1:numel(iY),[],@(x){ians(x)});
celldisp(w)
uj5u.com熱心網友回復：
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
const int N = 100001;
const int inf = 0x3f3f3f3f;
struct node {
int v, w;
node() {
}
node(int vv, int ww) {
v = vv;
w = ww;
}
};
vector<node> g[N];
int n, m, s;
int d[N];
set<pair<int, int> > min_heap;
int main() {
cin >> n >> m >> s;
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
g[u].push_back(node(v, w));
g[v].push_back(node(u, w));
}
memset(d, 0x3f, sizeof(d));
d[s] = 0;
min_heap.insert(make_pair(0,s));
while (min_heap.size()){
int mind=min_heap.begin()->first;
int v=min_heap.begin()->second;
min_heap.erase(min_heap.begin());
for (int i=0;i<g[v].size();i++){
if (d[g[v][i].v]>d[v]+g[v][i].w){
min_heap.erase(make_pair(d[g[v][i].v],g[v][i].v));
d[g[v][i].v] = d[v] + g[v][i].w;
min_heap.insert(make_pair(d[g[v][i].v], g[v][i].v));
}
}
}
for (int i = 1; i <= n; i++) {
cout << d[i] << " ";
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/14268.html
標籤：新手樂園
下一篇：proteus仿真 LED交通燈