題意：給定n個點，將所有點用一條線連起來，使得線最短。

分析：用d[i][j]代表走過了1~max(i，j)之間的點。dist表示兩點間的距離。作者的代碼可謂神仙代碼，細看才發現邏輯的奧妙。

#include<iostream> #include<string.h> #include<sstream> #include<set> #include<algorithm> #include<vector> #include<map> #include<queue> #include<math.h> using namespace std; const int maxn = 50 + 5; double x[maxn], y[maxn], dist[maxn][maxn], d[maxn][maxn];//離散化 int main() {int n;while (cin >> n&&n) {for (int i = 1; i <= n; i++) {cin >> x[i] >> y[i];}for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)dist[i][j] = sqrt((x[i] - x[j])*(x[i] - x[j]) + (y[i] - y[j])*(y[i] - y[j]));for(int i=n-1;i>=2;i--)for (int j = 1; j < i; j++) {if (i == n - 1)d[i][j] = dist[i][n] + dist[j][n];else d[i][j] = min(dist[i + 1][i] + d[i + 1][j], dist[j][i + 1] + d[i + 1][i]);//強制新加入的點小于被連接的點}printf("%.2lf\n", dist[1][2] + d[2][1]);}return 0; }

?

總結

以上是生活随笔為你收集整理的uva1347Tour的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。