沙河网站建设/搜狗搜索旧版本

思路：
20分：
直接考虑用dfs暴搜完事
100分：
感性理解一下题目，从1~n再从 n_{1，转换一下就成了1}n的两条不同路径之和最短的问题。
类似提高组2008年传纸条。
设f[i][j]为第一条路走到i号点，第二条路径走到第j号点的最短路径和。为了保证不出现两路相交的情况，即：f[i][i]。每次使用f[i][j]去更新max(i,j)+1,
所以动态转移方程为：
$$f[1][1]=0;k=max(i,j)+1dis(i,j)表示从i点到j点的距离$$
$$f[k][j]=max(f[k][j],f[i][j]+dis(i,k))$$
$$f[i][k]=max(f[i][k],f[i][j]+dis(j,k))$$
对于b1，b2和k - 1 == n的情况，我们只需要将点强制转换到特殊点即上述三点上。

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>using namespace std;const int N = 1e3 + 10;
int n, b1, b2;
double f[N][N], x[N], y[N];double d(int a, int b) {return sqrt((x[a] - x[b]) * (x[a] - x[b]) * 1.0 + (y[a] - y[b]) * (y[a] - y[b]) * 1.0);}int main()
{freopen("path.in","r",stdin);freopen("path.out","w",stdout);scanf("%d%d%d", &n, &b1, &b2);for(int i = 1; i <= n; i++) scanf("%lf%lf", &x[i], &y[i]);memset(f, 0x7f, sizeof(f));f[1][1] = 0;for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++){if(i == j && i != 1) continue;int k = max(i, j) + 1;if(k > n){if(i < n) f[n][n] = min(f[n][n], f[i][j] + d(i, n));if(j < n) f[n][n] = min(f[n][n], f[i][j] + d(j, n));}else{if(k != b2 + 1) f[k][j] = min(f[k][j], f[i][j] + d(i, k));if(k != b1 + 1) f[i][k] = min(f[i][k], f[i][j] + d(j, k));}}printf("%.2lf\n", f[n][n]);return 0;
}