Gym 100851F Froggy Ford(dijkstra)

题意

有条宽为w的河流，两岸分别在x = 0, x = w处，河中间有n个石板。在河的一岸有一只青蛙想通过石板跳到对岸去。现在可以在河 中间某个位置多加一块石板，使得在单步跳跃中的最大值最小。

思路

Dijkstra变形，用两维来表示是否路径中使用过额外的石板。dis[0][u]表示没使用额外石板的最大最小，dis[1][u]表示使 用额外石板的最大最小。然后就用Dijkstra格式进行转移了。 /***************************************** Author :Crazy_AC(JamesQi) Time :2016 File Name : *****************************************/ // #pragma comment(linker, "/STACK:1024000000,1024000000") #include <iostream> #include <algorithm> #include <iomanip> #include <sstream> #include <string> #include <stack> #include <queue> #include <deque> #include <vector> #include <map> #include <set> #include <cstdio> #include <cstring> #include <cmath> #include <cstdlib> #include <climits> using namespace std; #define MEM(x,y) memset(x, y,sizeof x) #define pk push_back #define lson rt << 1 #define rson rt << 1 | 1 #define bug cout << "BUG HERE\n" #define ALL(v) (v).begin(), (v).end() #define lowbit(x) ((x)&(-x)) #define Unique(x) sort(ALL(x)); (x).resize(unique(ALL(x)) - (x).begin()) #define BitOne(x) __builtin_popcount(x) #define showtime printf("time = %.15f\n",clock() / (double)CLOCKS_PER_SEC) #define Rep(i, l, r) for (int i = l;i <= r;++i) #define Rrep(i, r, l) for (int i = r;i >= l;--i) typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> ii; typedef pair<ii,int> iii; const double eps = 1e-8; const double pi = 4 * atan(1); const int inf = 1 << 30; const int INF = 0x3f3f3f3f; const int MOD = 1e9 + 7; int nCase = 0; const int maxn = 1e3 + 123; struct point { double x, y; void read() { scanf("%lf%lf", &x, &y); } double operator ^ (const point& rhs) { return sqrt((x - rhs.x) * (x - rhs.x) + (y - rhs.y) * (y - rhs.y)); } }a[maxn]; struct Edge { int v, nxt; double dis; }e[maxn*maxn*4]; int head[maxn], ecnt; void inline addedge(int u,int v,double dis) { e[ecnt] = Edge{v, head[u], dis}, head[u] = ecnt++; e[ecnt] = Edge{u, head[v], dis}, head[v] = ecnt++; } double dis[2][maxn]; int n, w; struct node { int u; double md; bool used; point o; bool operator < (const node& rhs) const { return md > rhs.md || (md == rhs.md && used > rhs.used); // return md > rhs.md; } }; void gao() { point ans; double m = INF; priority_queue<node> que; Rep(i, 0, n + 1) dis[0][i] = dis[1][i] = INF; que.push(node{0, 0, false, point{0, 0}}); dis[0][0] = 0; while(!que.empty()) { node temp = que.top(); que.pop(); int u = temp.u; if (u == n + 1) { printf("%.12lf %.12lf\n", temp.o.x, temp.o.y); return ; // if (temp.md < m) { // m = temp.md; // ans.x = temp.o.x; // ans.y = temp.o.y; // } continue; } for (int i = head[u]; ~i;i = e[i].nxt) { int v = e[i].v; if (v == 0) continue; if (temp.used) { if (dis[1][v] > max(temp.md, e[i].dis)) { dis[1][v] = max(temp.md, e[i].dis); que.push(node{v, dis[1][v], true, temp.o}); } }else { double x, y; //边界处理，容易错 if (u != 0 && v != n + 1) { x = (a[u].x + a[v].x) / 2.0; y = (a[u].y + a[v].y) / 2.0; } if (u != 0 && v == n + 1) { x = (a[u].x + w) / 2.0; y = a[u].y; } if (u == 0 && v == n + 1) { x = w / 2.0; y = 0; } if (u == 0 && v != n + 1) { x = a[v].x / 2.0; y = a[v].y; } // printf("[%.2lf, %.2lf]\n", x, y); if (dis[0][v] > max(temp.md, e[i].dis)) { dis[0][v] = max(temp.md, e[i].dis); que.push(node{v, dis[0][v], false, point{0, 0}}); } if (dis[1][v] > max(temp.md, e[i].dis / 2.0)) { dis[1][v] = max(temp.md, e[i].dis / 2.0); que.push(node{v, dis[1][v], true, point{x, y}}); } } } } printf("%.12lf %.12lf\n", ans.x, ans.y); } int main(int argc, const char * argv[]) { // freopen("in.txt","r",stdin); // freopen("out.txt","w",stdout); freopen("froggy.in","r",stdin); freopen("froggy.out","w",stdout); while(~scanf("%d%d", &w, &n)) { Rep(i, 1, n) a[i].read(); memset(head, -1, sizeof head), ecnt = 0; int vs = 0, vt = n + 1; addedge(vs, vt, w); Rep(i, 1, n) { addedge(vs, i, a[i].x); addedge(i, vt, w - a[i].x); Rep(j, i + 1, n) { addedge(i, j, a[i] ^ a[j]); } } if (n == 0) { printf("%.12lf 0\n", w / 2.0); continue; } gao(); } // showtime; return 0; }