POJ2253最短路

給出n个点的坐标，问点1到点2的所有路径中，两点最大距离的最小值是多少。 其实这种最小化最大值的题，用二分+dj应该没问题，但是其实还有更简单的方法，只需要改变松弛操作即可。

最短路经典松弛操作：

if (dis[v] > dis[u] + w)
dis[v] = dis[u] + w;

我们从本质出发，为什么这样更新呢？因为我们求最短路时最后想要的是最小的总dis。回到这题，我们最后想要的每条路径上所有小段的dis中的最小值。那么只需改变松弛操作为:

if (dis[v] > max(dis[u] , w))
dis[v] = max(dis[u] , w);

另外，这题n=200的数据范围，可以用Floyd写，更简单。
Dijkstra代码：

/*
* @Author: hesorchen
* @Date: 2020-04-14 10:33:26
* @LastEditTime: 2020-05-06 09:33:04
* @Link: https://hesorchen.github.io/
*/
#include <map>
#include <set>
#include <list>
#include <queue>
#include <deque>
#include <cmath>
#include <stack>
#include <vector>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define endl 'n'
#define PI cos(-1)
#define PB push_back
#define ll long long
#define INF 0x3f3f3f3f
#define mod 1000000009
#define lowbit(abcd) (abcd & (-abcd))
#define fre

{

freopen("in.txt", "r", stdin);

freopen("out.txt", "w", stdout); 
}
struct node
{
double w;
int v, next;
} edge[40010];
int head[210];
double dis[210];
int vis[210];
struct node2
{
double x, y;
} p[210];
struct node3
{
int u;
double w;
bool operator<(node3 const b) const
{
return w > b.w;
}
};
priority_queue<node3> q;
int ct = 1;
void add(int u, int v, double w)
{
edge[ct].v = v;
edge[ct].w = w;
edge[ct].next = head[u];
head[u] = ct++;
}
inline double distant(node2 a, node2 b)
{
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
void dj()
{
fill(dis, dis + 210, 1000000000);
fill(vis, vis + 210, 0);
dis[1] = 0;
q.push(node3{1, 0});
while (!q.empty())
{
int u = q.top().u;
q.pop();
for (int i = head[u]; i; i = edge[i].next)
{
int v = edge[i].v;
if (dis[v] > max(dis[u], edge[i].w))
{
dis[v] = max(dis[u], edge[i].w);
q.push(node3{v, dis[v]});
}
}
}
}
int main()
{
// fre;
int n;
int cas = 1;
while (cin >> n)
{
if (!n)
break;
ct = 1;
fill(head, head + 210, 0);
for (int i = 1; i <= n; i++)
cin >> p[i].x >> p[i].y;
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++)
{
add(j, i, distant(p[i], p[j]));
add(i, j, distant(p[i], p[j]));
}
dj();
printf("Scenario #%dnFrog Distance = ", cas++);
printf("%.3fnn", dis[2]);
}
return 0;
}

最后

以上就是爱撒娇鸡翅为你收集整理的POJ2253最短路的全部内容，希望文章能够帮你解决POJ2253最短路所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。