Go to diff to previous submission
#include <algorithm> #include <cctype> #include <cmath> #include <complex> #include <cstdio> #include <cstring> #include <iomanip> #include <iostream> #include <list> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> using namespace std; #define DEBUG(x) cerr << ">>> " << #x << " : " << x << endl; #define REP(i,a) for (int i = 0; i < (a); ++i) #define FOR(i,a,b) for (int i = (a); i <= (b); ++i) #define FORD(i,a,b) for (int i = (a); i >= (b); --i) inline bool EQ(double a, double b) { return fabs(a-b) < 1e-9; } const int INF = 1<<29; typedef long long ll; ////////////////////////////////// #define MAXN 1100 #define MAXC 2200 #define MAXD 10100 int N; double S, T; map<ll, int> n2i_map; ll i2n_map[MAXC]; int iCnt; vector<int> way[MAXC]; bool visited[MAXC][MAXC]; double totDist[MAXC][MAXC]; typedef priority_queue<pair<double, pair<int, int> > > qType; qType toVisit; void clear_all() { n2i_map.clear(); iCnt = 0; REP(i,MAXC) way[i].clear(); REP(i,MAXC) REP(j, MAXC) visited[i][j] = false; REP(i,MAXC) REP(j, MAXC) totDist[i][j] = 1.0 / 0.0; toVisit = qType(); } int p2i(int x, int y, int z) { ll p = x; p *= MAXD; p += y; p *= MAXD; p += z; map<ll, int>::iterator iter = n2i_map.find(p); if (iter != n2i_map.end()) return iter->second; n2i_map[p] = iCnt; i2n_map[iCnt] = p; return iCnt++; } ll i2n(int i) { return i2n_map[i]; } int n2x(ll n) { return (n / MAXD) / MAXD; } int n2y(ll n) { return (n / MAXD) % MAXD; } int n2z(ll n) { return n % MAXD; } double dist(int i1, int i2) { ll n1 = i2n(i1), n2 = i2n(i2); double x1 = n2x(n1), y1 = n2y(n1), z1 = n2z(n1); double x2 = n2x(n2), y2 = n2y(n2), z2 = n2z(n2); double dx = x1-x2, dy = y1-y2, dz = z1-z2; return sqrt(dx*dx+dy*dy+dz*dz); } double distT(int i1, int i2) { return dist(i1, i2) / S; } double ang(int i1, int d1, int i2, int d2) { ll n1i = i2n(i1), n2i = i2n(i2); ll n1d = i2n(d1), n2d = i2n(d2); double x1i = n2x(n1i), y1i = n2y(n1i), z1i = n2z(n1i); double x2i = n2x(n2i), y2i = n2y(n2i), z2i = n2z(n2i); double x1d = n2x(n1d), y1d = n2y(n1d), z1d = n2z(n1d); double x2d = n2x(n2d), y2d = n2y(n2d), z2d = n2z(n2d); double dx1 = x1d-x1i, dy1 = y1d-y1i, dz1 = z1d-z1i; double dx2 = x2d-x2i, dy2 = y2d-y2i, dz2 = z2d-z2i; double num = dx1*dx2 + dy1*dy2 + dz1*dz2; double den = dist(i1, d1) * dist(i2, d2); return acos(num / den) * 180.0 / M_PI; } double angT(int i1, int d1, int i2, int d2) { return ang(i1, d1, i2, d2) / T; } int main() { while (scanf("%d%lf%lf", &N, &S, &T) == 3) { clear_all(); int Si, Fi; { int x, y, z; scanf("%d%d%d", &x, &y, &z); Si = p2i(x, y, z); scanf("%d%d%d", &x, &y, &z); Fi = p2i(x, y, z); } REP(i,N) { int x, y, z; scanf("%d%d%d", &x, &y, &z); int i1 = p2i(x, y, z); scanf("%d%d%d", &x, &y, &z); int i2 = p2i(x, y, z); way[i1].push_back(i2); way[i2].push_back(i1); } if (Si == Fi) { printf("%lf\n", 0.0); continue; } for (unsigned int jj = 0; jj < way[Si].size(); ++jj) { int toD = way[Si][jj]; totDist[Si][toD] = 0; toVisit.push(make_pair(0, make_pair(Si, toD))); } while (!toVisit.empty()) { //printf("dist %lf\n", -toVisit.top().first); pair<int, int> pr = toVisit.top().second; toVisit.pop(); int at = pr.first, d = pr.second; if (at == Fi) break; if (visited[at][d]) continue; //printf("vis %d %d\n", at, d); visited[at][d] = true; double dT = distT(at, d); if (d == Fi) { if (totDist[at][d]+dT < totDist[d][0]) { totDist[d][0] = totDist[at][d]+dT; toVisit.push(make_pair(-totDist[d][0], make_pair(d, 0))); } continue; } for (unsigned int jj = 0; jj < way[d].size(); ++jj) { int toD = way[d][jj]; if (visited[d][toD]) continue; //printf(" try %d %d\n", d, toD); double aT = angT(at, d, d, toD); if (totDist[at][d]+dT+aT < totDist[d][toD]) { //printf(" go %d %d\n", d, toD); totDist[d][toD] = totDist[at][d]+dT+aT; toVisit.push(make_pair(-totDist[d][toD], make_pair(d, toD))); } } } printf("%lf\n", totDist[Fi][0]); } return 0; }