题意：
现在有一条河，河中有n个石头，你需要从河的一端到河的另一端。现在你有一次机会在任意位置放置一个石头，请问石头放在哪里可以使过河的最长路径最短。请输出放置的石头坐标。
思路：
n的规模是(1e3)，所以可以做到(n^2)的算法，我们把起点和终点也当做一块石头，基于贪心的思想，可以知道使最长路径最短的放法一定是在两个石子的中间点放。先预处理出起点到各个点的最短路和终点反跑到各个点的最短路，然后(n^2)枚举两个石头间距并将其缩短一半，更新答案。
#include
using namespace std;
#define rep(i, a, n) for(int i = a; i < n; i++)
#define all(x) x.begin(), x.end()
#define pb push_back
#define ios ios::sync_with_stdio(false);cin.tie(0);
#define debug(x) cout << x << endl;
#define SZ(x) (int)x.size()
typedef long long LL;
typedef unsigned long long ULL;
typedef pair PII;
const int inf = 0x3f3f3f3f;
const double INF = 1e20;
void read(int &x) {int s = 0, f = 1; char ch = getchar(); while(!isdigit(ch)) {f = (ch == '-' ? -1 : f); ch = getchar();} while(isdigit(ch)) {s = s * 10 + ch - '0'; ch = getchar();} x = s * f;}
const int N = 1005;
struct node {
double val;
int id;
bool operator < (const node& a) const {
return val > a.val;
}
};
double e[N][N];
double x[N], y[N];
double dis1[N], dis2[N];
int vis[N];
int n;
double ww;
double dis(double a, double b, double c, double d)
{
return sqrt((b - a) * (b - a) + (d - c) * (d - c));
}
void dij1(int st)
{
priority_queue q;
rep(i, 1, n + 1) dis1[i] = INF;
memset(vis, 0, sizeof vis);
dis1[st] = 0;
q.push({dis1[st], st});
while(q.size())
{
node tmp = q.top();
q.pop();
int u = tmp.id;
double dist = tmp.val;
if(vis[u]) continue;
vis[u] = 1;
rep(v, 1, n + 1)
{
if(u == v) continue;
if(!vis[v] && dis1[v] > max(dist, e[u][v]))
{
dis1[v] = max(dist, e[u][v]);
q.push({dis1[v], v});
}
}
}
}
void dij2(int st)
{
priority_queue q;
rep(i, 1, n + 1) dis2[i] = INF;
memset(vis, 0, sizeof vis);
dis2[st] = 0;
q.push({dis2[st], st});
while(q.size())
{
node tmp = q.top();
q.pop();
int u = tmp.id;
double dist = tmp.val;
if(vis[u]) continue;
vis[u] = 1;
rep(v, 1, n + 1)
{
if(u == v) continue;
if(!vis[v] && dis2[v] > max(dist, e[u][v]))
{
dis2[v] = max(dist, e[u][v]);
q.push({dis2[v], v});
}
}
}
}
signed main()
{
freopen("froggy.in", "r", stdin);
freopen("froggy.out", "w", stdout);
scanf("%lf%d", &ww, &n);
if(n == 0)
printf("%.3lf %.3lf\n", ww / 2.0, 0.0);
else
{
rep(i, 2, n + 2)
scanf("%lf %lf", &x[i], &y[i]);
n += 2; //1是起点，n是终点
e[1][n] = e[n][1] = ww;
rep(i, 2, n)
{
e[1][i] = e[i][1] = x[i];
e[n][i] = e[i][n] = ww - x[i];
}
rep(i, 2, n)
rep(j, i + 1, n)
e[i][j] = e[j][i] = dis(x[i], x[j], y[i], y[j]);
dij1(1);
dij2(n);
double res = INF;
double resx, resy;
rep(i, 2, n)
rep(j, 2, n)
{
if(i == j) continue;
if(res > max(e[i][j] / 2.0, max(dis1[i], dis2[j])))
{
res = max(e[i][j] / 2.0, max(dis1[i], dis2[j]));
resx = (x[i] + x[j]) / 2.0, resy = (y[i] + y[j]) / 2.0;
}
}
rep(i, 2, n)
{
if(res > max(x[i] / 2.0, dis2[i]))
{
res = max(x[i] / 2.0, dis2[i]);
resx = x[i] / 2.0, resy = y[i];
}
if(res > max((ww - x[i]) / 2.0, dis1[i]))
{
res = max((ww - x[i]) / 2.0, dis1[i]);
resx = x[i] + (ww - x[i]) / 2.0, resy = y[i];
}
}
printf("%.3lf %.3lf\n", resx, resy);
}
}
Original: https://www.cnblogs.com/DM11/p/16654955.html
Author: DM11
Title: GYM100851 F-Froggy Ford（最短路铜牌题）
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/604042/
转载文章受原作者版权保护。转载请注明原作者出处！