2013年9月3日

UVa 10389 - Subway

```#include <cstdio>
#include <cmath>
#include <sstream>
#include <vector>
#include <queue>
#include <map>
#define PB push_back
#define MP make_pair
using namespace std;

typedef pair<int, int> P;

struct State {
State(P p, double need) : p(p), need(need) {}
bool operator<(const State & other) const {
return need > other.need;
}
P p;
double need;
};

const double mpm[2] = {10000 / 60.0, 40000 / 60.0};

inline double dis(P & a, P & b) {
int dx = a.first - b.first, dy = a.second - b.second;
return sqrt(dx * dx + dy * dy);
}

int main() {
char temp[9999];
gets(temp);
int T;
sscanf(temp, "%d", &T);
gets(temp);
while (T--) {
gets(temp);
int sx, sy, ex, ey;
sscanf(temp, "%d%d%d%d", &sx, &sy, &ex, &ey);
P s = MP(sx, sy), e = MP(ex, ey);
vector<P> walk;
map<P, vector<P> > next;
walk.PB(e);
while (gets(temp) && *temp) {
istringstream ss(temp);
int x, y;
vector<P> v;
while (ss >> x >> y) {
if (x < 0) {
break;
}
v.PB(MP(x, y));
}
for (int i = 0; i < v.size(); i++) {
walk.PB(v[i]);
if (i) {
next[v[i]].PB(v[i - 1]);
}
if (i < v.size() - 1) {
next[v[i]].PB(v[i + 1]);
}
}
}
priority_queue<State> pq;
map<P, double> best;
best[s] = 0;
pq.push(State(s, 0));
while (!pq.empty()) {
P now = pq.top().p;
double need = pq.top().need;
pq.pop();
if (now == e) {
printf("%.0lf\n", need);
break;
}
for (int i = 0; i < walk.size(); i++) {
P & j = walk[i];
if (now != j) {
double nextNeed = need + dis(now, j) / mpm[0];
if (best.find(j) == best.end() || nextNeed < best[j]) {
pq.push(State(j, nextNeed));
best[j] = nextNeed;
}
}
}
for (int i = 0; i < next[now].size(); i++) {
P & j = next[now][i];
if (now != j) {
double nextNeed = need + dis(now, j) / mpm[1];
if (best.find(j) == best.end() || nextNeed < best[j]) {
pq.push(State(j, nextNeed));
best[j] = nextNeed;
}
}
}
}
if (T) {
puts("");
}
}
return 0;
}
```