传送门
建图麻烦，建完图搞一遍Floyd就好了。
——代码
1 #include <iostream> 2 #include <cstdio> 3 #include <cmath> 4 5 using namespace std; 6 7 int n, s, a, b; 8 int t, x[401][5], y[402][5], T[401]; 9 double map[401][401], ans; 10 11 inline int square(int ax) 12 15 16 inline int dis(int ax, int ay, int bx, int by) 17 20 21 int main() 22 41 else if(dis(x[i][1], y[i][1], x[i][3], y[i][3]) > dis(x[i][3], y[i][3], x[i][2], y[i][2]) 42 && dis(x[i][1], y[i][1], x[i][3], y[i][3]) > dis(x[i][2], y[i][2], x[i][1], y[i][1])) 43 47 else if(dis(x[i][2], y[i][2], x[i][3], y[i][3]) > dis(x[i][3], y[i][3], x[i][1], y[i][1]) 48 && dis(x[i][2], y[i][2], x[i][3], y[i][3]) > dis(x[i][2], y[i][2], x[i][1], y[i][1])) 49 53 map[4 * i][4 * i + 1] = map[4 * i + 1][4 * i] = sqrt(dis(x[i][1], y[i][1], x[i][2], y[i][2])) * T[i]; 54 map[4 * i][4 * i + 2] = map[4 * i + 2][4 * i] = sqrt(dis(x[i][1], y[i][1], x[i][3], y[i][3])) * T[i]; 55 map[4 * i][4 * i + 3] = map[4 * i + 3][4 * i] = sqrt(dis(x[i][1], y[i][1], x[i][4], y[i][4])) * T[i]; 56 map[4 * i + 1][4 * i + 2] = map[4 * i + 2][4 * i + 1] = sqrt(dis(x[i][2], y[i][2], x[i][3], y[i][3])) * T[i]; 57 map[4 * i + 1][4 * i + 3] = map[4 * i + 3][4 * i + 1] = sqrt(dis(x[i][2], y[i][2], x[i][4], y[i][4])) * T[i]; 58 map[4 * i + 2][4 * i + 3] = map[4 * i + 3][4 * i + 2] = sqrt(dis(x[i][3], y[i][3], x[i][4], y[i][4])) * T[i]; 59 for(j = 0; j < 4 * i; j++) 60 for(k = 4 * i; k < 4 * i + 4; k++) 61 map[k][j] = map[j][k] = sqrt(dis(x[j / 4][j % 4 + 1], y[j / 4][j % 4 + 1], x[k / 4][k % 4 + 1], y[k / 4][k % 4 + 1])) * t; 62 } for(i = 0; i < 4 * s; i++) map[i][i] = 0; 64 for(k = 0; k < 4 * s; k++) 65 for(i = 0; i < 4 * s; i++) 66 for(j = 0; j < 4 * s; j++) 67 map[i][j] = min(map[i][j], map[i][k] + map[k][j]); 68 for(i = 4 * a 4; i < 4 * a; i++) 69 for(j = 4 * b 4; j < 4 * b; j++) 70 ans = min(ans, map[i][j]); 71 printf("%.1f\n", ans); 72 } 73 return 0; 74 }View Code
上一篇：[luoguP1168]中位数（主席树+离散化）
下一篇：[luoguP1352] 没有上司的舞会（DP）
最短路 Floyd
