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 64 65 66 67 68 69 70 71 72 73
| #include <iostream> #include <math.h> #include <queue> #include <string.h>
using namespace std; const int maxn = 305; const int MAX = 1<<30;
struct node { double x,y; } point[maxn];
bool vis[maxn]; double grid[maxn][maxn]; double dist[maxn]; int n;
double dis(node a,node b) { double dx = a.x - b.x; double dy = a.y - b.y; return sqrt(dx*dx+dy*dy); } void spfa() { for (int i=1; i<=n; i++) dist[i] = MAX; memset(vis,0,sizeof vis); queue<int> que; vis[1] = 1; dist[1] = 0; que.push(1); while (!que.empty()) { int cur = que.front(); que.pop(); vis[cur] = 0; for (int i=1; i<=n; i++) { if (dist[i] > dist[cur] + grid[cur][i]) { dist[i] = dist[cur] + grid[cur][i]; if (!vis[i]) { vis[i] = 1; que.push(i); } } } } } int main() {
double v1 = 10000.0/60; double v2 = 40000.0/60; cin >> point[1].x >> point[1].y >> point[2].x >> point[2].y; for (int i=1; i<maxn; i++) for (int j=1; j<maxn; j++) { if (i == j) grid[i][j] = 0; else grid[i][j] = MAX; } double dx,dy; n = 2; int cnt = 3; while (scanf("%lf%lf",&dx,&dy) != EOF) { if (dx == -1 && dy == -1) { cnt = n+1; continue; } n++; point[n].x = dx; point[n].y = dy; if (cnt != n) { grid[n][n-1] = grid[n-1][n] = min(grid[n][n-1],dis(point[n],point[n-1])/v2); } } for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) grid[i][j] = grid[j][i] = min(grid[i][j],dis(point[i],point[j])/v1); spfa(); printf("%.0lf\n",dist[2]); return 0; }
|