原题链接：[NOIP2001 提高组] Car 的旅行路线 - 洛谷
AC代码：
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
typedef pair<int, int> PII;
const double pi = acos(-1.0);
#define rep(i, n) for (int i = 1; i <= (n); ++i)
#define rrep(i, n) for (int i = n; i >= (1); --i)
typedef long long ll;
#define sqar(x) ((x)*(x))const int N = 410;int n, s,a, b;
double t;
double fee[110];
double res[N][N];
int cnt;struct node
{double x, y;int city;
}Node[N];void init()
{cnt = 0;double x1, y1, x2, y2, x3, y3, x4, y4, T;rep(i, s){scanf("%lf %lf %lf %lf %lf %lf %lf", &x1, &y1, &x2, &y2, &x3, &y3, &T);fee[i] = T;if(sqar(x1 - x2) + sqar(y1 - y2) + sqar(x1 - x3) + sqar(y1 - y3) == sqar(x2 - x3) + sqar(y2 - y3)){x4 = x2 + x3 - x1;y4 = y2 + y3 - y1;}else if(sqar(x2 - x1) + sqar(y2 - y1) + sqar(x2 - x3) + sqar(y2 - y3) == sqar(x1 - x3) + sqar(y1 - y3)){x4 = x1 + x3 - x2;y4 = y1 + y3 - y2;}else if(sqar(x3 - x2) + sqar(y3 - y2) + sqar(x3 - x1) + sqar(y3 - y1) == sqar(x1 - x2) + sqar(y1 - y2)){x4 = x1 + x2 - x3;y4 = y1 + y2 - y3;}Node[++cnt] = {x1, y1, i};Node[++cnt] = {x2, y2, i};Node[++cnt] = {x3, y3, i};Node[++cnt] = {x4, y4, i};}rep(i, cnt)rep(j, cnt){if(Node[i].city == Node[j].city){res[i][j] = sqrt(sqar(Node[i].x - Node[j].x) + sqar(Node[i].y - Node[j].y)) * fee[Node[i].city];}else{res[i][j] = sqrt(sqar(Node[i].x - Node[j].x) + sqar(Node[i].y - Node[j].y)) * t;}}
}int main()
{scanf("%d", &n);while(n--){scanf("%d %lf %d %d", &s, &t, &a, &b);init();rep(k, cnt)rep(i, cnt)rep(j, cnt){res[i][j] = min(res[i][j], res[i][k] + res[k][j]);}double ans = -1;for(int i = (a - 1) * 4 + 1; i <= a * 4; i++)for(int j = (b - 1) * 4 + 1; j <= b * 4; j++){if(ans == -1) ans = res[i][j];else ans = min(ans, res[i][j]);}printf("%.1lf", ans);}return 0;
}