#pragma GCC optimize("O3") #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; using P = pair; using T = tuple; template inline T chmax(T &a, const T b) {return a = (a < b) ? b : a;} template inline T chmin(T &a, const T b) {return a = (a > b) ? b : a;} constexpr int MOD = 1e9 + 7; constexpr int inf = 1e9; constexpr long long INF = 1e18; constexpr double pi = acos(-1); constexpr double EPS = 1e-10; int dx[] = {1, 0, -1, 0}; int dy[] = {0, 1, 0, -1}; int n; double dijkstra(int s, vector>> &G){ vector dist(n, INF); priority_queue, vector>, greater>> que; dist[s] = 0; que.emplace(0, s); while(que.size()){ double ccost; int cv; tie(ccost, cv) = que.top(); que.pop(); if(dist[cv] < ccost) continue; for(auto nxt : G[cv]){ int nv; double ncost; tie(nv, ncost) = nxt; if(dist[cv] + ncost < dist[nv]){ dist[nv] = dist[cv] + ncost; que.emplace(dist[nv], nv); } } } return dist[n-1]; } int main(){ cin.tie(0); ios::sync_with_stdio(false); cin>>n; vector x(n), y(n); for(int i=0; i>x[i]>>y[i]; ll ng = 0, ok = 1e15; while(ok - ng > 1){ ll mid = (ng + ok) / 2; mid *= 10; vector>> G(n); for(int i=0; i (double)mid + EPS) continue; G[i].emplace_back(j, cdist); } } double ans = dijkstra(0, G); if(ans == INF) ng = mid / 10; else ok = mid / 10; } cout << ok * 10 << endl; return 0; }