#2 数据本地能过但是交上去不开 O2 都过不了

Code:

#include <bits/stdc++.h>
using namespace std;
int x[405][5], y[405][5];
double dis[405][405];
int tr[405];
int s, t, a, b;
int tn;
pair<int, int> get4(int, int, int, int, int, int);
inline bool is_vertical(int, int, int, int);
inline double S(int, int, int, int);
inline int N(int a, int b){return (a-1)*4+b;}
int main(){
	scanf("%d", &tn);
	while(tn--){
		scanf("%d %d %d %d", &s, &t, &a, &b);
		memset(dis, 0, sizeof(dis));
	    for(int i = 1; i <= s; i++){
	        for(int j = 1; j <= 3; j++) scanf("%d %d", &x[i][j], &y[i][j]);
	        scanf("%d", &tr[i]);
	        pair<int, int> xy4 = get4(x[i][1], y[i][1], x[i][2], 
	                                  y[i][2], x[i][3], y[i][3]);
	        x[i][4] = xy4.first, y[i][4] = xy4.second;
	        for(int j = 1; j <= 4; j++){
	            for(int k = j; k <= 4; k++){
	                if(j == k) dis[N(i, j)][N(i, k)] = dis[N(i, k)][N(i, j)] = 0;
	                else dis[N(i, j)][N(i, k)] = dis[N(i, k)][N(i, j)] = tr[i]*S(x[i][j], y[i][j], x[i][k], y[i][k]);
	            }
	        }
	        for(int j = 1; j <= 4; j++){
	            for(int k = 1; k < i; k++){
	                for(int l = 1; l <= 4; l++){
	                    dis[N(i, j)][N(k, l)] = dis[N(k, l)][N(i, j)] = t*S(x[i][j], y[i][j], x[k][l], y[k][l]);
	                }
	            }
	        }
	    }
	    for(int k = 1; k <= s*4; k++){
	        for(int i = 1; i <= s*4; i++){
	            for(int j = 1; j <= s*4; j++){
	                dis[i][j] = min(dis[i][j], dis[i][k]+dis[k][j]);
	            }
	        }
	    }
	    double ans = 1e15;
	    for(int i = 1; i <= 4; i++){
	        for(int j = 1; j <= 4; j++){
	            ans = min(ans, dis[N(a, i)][N(b, j)]);
	        }
	    }
	    printf("%.1llf\n", ans);
	}
    
}
pair<int, int> get4(int _x1, int _y1, int _x2, 
                    int _y2, int _x3, int _y3){
    int _x4, _y4;
    int xAB = (_x1-_x2), yAB = (_y1-_y2); // edge AB
    int xAC = (_x2-_x3), yAC = (_y2-_y3); // edge AC
    int xBC = (_x1-_x3), yBC = (_y1-_y3); // edge BC
    if(is_vertical(xAB, yAB, xAC, yAC)) _x4 = _x3-(_x1-_x2), _y4 = _y3-(_y1-_y2);
    else if(is_vertical(xAC, yAC, xBC, yBC)) _x4 = _x1-(_x3-_x2), _y4 = _y1-(_y3-_y2);
    else if(is_vertical(xAB, yAB, xBC, yBC)) _x4 = _x1-(_x2-_x3), _y4 = _y1-(_y2-_y3);
    return make_pair(_x4, _y4);
}
inline bool is_vertical(int xA, int yA, int xB, int yB){
	if(fabs((double)xA/yA - (double)yB/xB) <= 1e6) return true;
	else return false;
}
inline double S(int a, int b, int c, int d){
    return sqrt((a-c)*(a-c)+(b-d)*(b-d));
}

数据：

Input:
1
3 10 1 3
2 2 2 1 1 2 10
2 12 12 2 22 12 1
22 22 22 32 32 22 10

Output:
214.1