题目传送门
题意:列车上行驶40, 其余走路速度10.问从家到学校的最短时间
分析:关键是建图:相邻站点的速度是40,否则都可以走路10的速度.读入数据也很变态.
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;const int N = 2e2 + 5;
const int E = N * N;
const double INF = 1e30;
struct Point {double x, y;
}p[N];
bool vis[N];
double d[N];
double w[N][N];
double sx, sy, ex, ey;
int tot;void Dijkstra(int s) {memset (vis, false, sizeof (vis));for (int i=1; i<=tot; ++i) {d[i] = INF;}d[s] = 0;for (int i=1; i<=tot; ++i) {double mn = INF; int x = -1;for (int j=1; j<=tot; ++j) {if (!vis[j] && mn > d[j]) mn = d[x=j];}if (x == -1) break;vis[x] = true;for (int j=1; j<=tot; ++j) {if (!vis[j] && d[j] > d[x] + w[x][j]) {d[j] = d[x] + w[x][j];}}}
}double squ(double x) {return x * x;
}double get_cost(Point p1, Point p2, int v) {double dis = sqrt (squ (p1.x - p2.x) + squ (p1.y - p2.y)) / 1000;return dis / v;
}int main(void) {while (scanf ("%lf%lf%lf%lf", &sx, &sy, &ex, &ey) == 4) {for (int i=1; i<N; ++i) {for (int j=1; j<N; ++j) {w[i][j] = INF;}}tot = 1;double x, y, l = tot + 1;p[tot].x = sx; p[tot].y = sy;while (scanf ("%lf%lf", &x, &y) == 2) {if (x == -1 && y == -1) {for (int i=l; i<tot; ++i) {double tim = get_cost (p[i], p[i+1], 40);if (w[i][i+1] > tim) {w[i][i+1] = w[i+1][i] = tim;}}l = tot + 1;continue;}p[++tot].x = x; p[tot].y = y;}p[++tot].x = ex; p[tot].y = ey;for (int i=1; i<tot; ++i) {for (int j=i+1; j<=tot; ++j) {double tim = get_cost (p[i], p[j], 10);if (w[i][j] > tim) {w[i][j] = w[j][i] = tim;}}}Dijkstra (1);printf ("%.0f\n", d[tot] * 60);}return 0;
}
