本文主要是介绍POJ 2253(dijkstra变形)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：点击打开链接
题目大意：第一个石头当起点，第二个石头当终点，问你到第二个石头的最短路中最长的那条路有多长。
题目思路：刚开始完全看不懂题目，然后百度一波看到要用dijkstra，还以为就是从石头一到石头二的最短路..自信满满的打出模板后，结果样例都过不去..后来实在没办法，去网上找了一波题解，还是有点看不懂，然后去找了大佬咨询了一波。原来这道题改了模板特别特别多的地方..dis数组存的不再是1到该点的最短路，而是1到该点最小的最长路.....而且在原来的模板中，vis[1]需要先改成1，但是这里不是，因为这里第一步就需要用1先松弛一波，如果初始化为1，那就直接把这一步跳了，然后就是dis的初始化不再是1到各点的距离，而是除了1更新为0，其他全部更新为inf，因为这样才能不断迭代出最小的最长路。刚开始太拘泥于模板，这些地方都没改过来，结果一直没de出来bug。然后这道题最核心最核心的一个代码就是dis[j]=min(dis[j],max(map1[u][j],dis[u]))，这步的目的是为了松弛，max函数要做的，就是取出如果经过这个转折点，需要走的最长路是多大，看看跟之前存的最大路比较，如果这个比较小，那就选择中转一波。这道题说实话还是挺难理解的，可以多看几篇博客体会一下，感觉颠覆了我对dijkstra的认知，原来模板还能改变幅度这么大....
温馨提示：此题在POJ上请使用C++编译器提交，而不是默认的G++！之前看到有博主提醒过了不以为意，结果wa掉了，de了半天bug没找出来，后来突然想起来这个提醒，就改用C++真的过了，非常无情
以下是代码：
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<math.h>
using namespace std;
#define inf 0x3f3f3f3f
struct node{int x,y;
}a[205];
double dis[205],map1[205][205];
int vis[205];
double juli(node x,node y){return sqrt(1.0*(x.x-y.x)*(x.x-y.x)+1.0*(x.y-y.y)*(x.y-y.y));
}
int main()
{int n,num=1;while(~scanf("%d",&n)&&n){for(int i=1;i<=n;i++){scanf("%d%d",&a[i].x,&a[i].y);}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){map1[i][j]=juli(a[i],a[j]);}}for(int i=1;i<=n;i++){dis[i]=inf;}memset(vis,0,sizeof(vis));int u;dis[1]=0;for(int i=1;i<n;i++){//cout<<"i"<<i<<endl;double min1=inf;for(int j=1;j<=n;j++){if(!vis[j]&&dis[j]<min1){u=j,min1=dis[j];}}vis[u]=1;for(int j=1;j<=n;j++){dis[j]=min(dis[j],max(map1[u][j],dis[u]));}}printf("Scenario #%d\nFrog Distance = %.3lf\n\n",num++,dis[2]);}return 0;
}
这篇关于POJ 2253(dijkstra变形)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
