例题9-3　旅行（Tour, ACM/ICPC SEERC 2005, UVa1347）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <set>
#include <map>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#include <deque>
#include <cstdio>
#include <string>
#include <vector>
#include <cctype>
#include <sstream>
#include <utility>
#include <cstring>
#include <cstdlib>
#include <functional>
#include <iostream>
#include <algorithm>
#define SF(a) scanf("%d", &a)
#define PF(a) printf("%dn", a)
#define SFF(a, b) scanf("%d%d", &a, &b)
#define SFFF(a, b, c) scanf("%d%d%d", &a, &b, &c)
#define SFFFF(a, b, c, d) scanf("%d%d%d%d", &a, &b, &c, &d)
#define CLEAR(a, b) memset(a, b, sizeof(a))
#define IN() freopen("in.txt", "r", stdin)
#define OUT() freopen("out.txt", "w", stdout)
#define FOR(i, a, b) for(int i = a; i < b; ++i)
#define LL long long
#define mod 10007
#define inf 100000007
#define eps 1e-12
using namespace std;
int buf[20] ;
int read() {
int x = 0; char ch = getchar(); bool f = 0;
while (ch < '0' || ch > '9') { if (ch == '-') f = 1; ch = getchar(); }
while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
return f ? -x : x;
}
void write(int x) {
if (!x) { putchar(48); return; }
int l = 0; if (x < 0) putchar('-'), x = -x;
while (x) buf[++l] = x % 10, x = x / 10;
while (l) putchar(buf[l--] + 48);
}
//-------------------------chc------------------------------//
const int maxn = 55;
double x[maxn], y[maxn], d[maxn][maxn], dis[maxn][maxn];
int main() {
int n;
while (~SF(n)) {
FOR(i, 1, n + 1) scanf("%lf%lf", &x[i], &y[i]);
FOR(i, 1, n + 1) FOR(j, 1, n + 1)
dis[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] = dis[i][n] + dis[j][n];
else d[i][j] = min(dis[i][i + 1] + d[i + 1][j], dis[j][i + 1] + d[i + 1][i]);
}
printf("%.2lfn", dis[1][2] + d[2][1]);
}
return 0;
}