POJ 2253-Frogger （Prim）

題目鏈接：Frogger

題意：兩只青蛙，A和B，A想到B哪裡去，但是A得彈跳有限制，所以不能直接到B，但是有其他的石頭作為過渡點，可以通過他們到達B，問A到B的所有路徑中，它彈跳最大的跨度的最小值

PS：最小生成樹過的，剛開始用Dijstra做，Kao，精度損失的厲害，對於Dijksra的變形不大會變啊，看了Discuss有人用最小生成樹過，我一劃拉，還真是，敲了，就過了，等會研究研究最短路的各種變形，有模板不會變，不會靈活應用，渣渣就是渣渣。

ME Time

1017Kb 0Ms

#include 
#include 
#include 
#include 
#include 
#include 
const int INF = 1e8;
const int N = 205;
using namespace std;
struct node{
    int x,y;
}g[N];
int n,vis[N];
double mapp[N][N],dis[N];
double Prim()
{
    int pos;
    double maxe=0,minn;
    for(int i=1;i<=n;i++)
    {
        dis[i]=mapp[1][i];
        vis[i]=0;
    }
    vis[1]=1;
    dis[1]=0;
    for(int i=1;i<=n;i++)
    {
        minn=INF;
        pos=1;
        for(int j=1;j<=n;j++)
           {
               if(!vis[j]&&dis[j]maxe)
            maxe=minn;
        if(pos==2) //如果當前構樹條件是2號哇，那麼直接返回，無其他路線了
            return maxe;
        vis[pos]=1;
        for(int j=1;j<=n;j++)
            if(!vis[j] &&mapp[pos][j] < dis[j])
            {
                dis[j] = mapp[pos][j];
            }
    }
    return dis[2];
}
void init(int i)
{
    double t;
    mapp[i][i]=0;
    for(int j=1;j<i;j++) {="" t="sqrt((g[i].x-g[j].x)*(g[i].x-g[j].x)+(g[i].y-g[j].y)*(g[i].y-g[j].y));" mapp[i][j]="t;" mapp[j][i]="t;" }="" int="" main()="" c="0;" double="" st;="" while(scanf("%d",&n),n)="" for(int="" i="1;i<=n;i++)" scanf("%d%d",&g[i].x,&g[i].y);="" init(i);="" st="Prim();" printf("scenario="" #%d\n",++c);="" printf("frog="" distance="%.3f\n\n&quot;,st);//看了Discuss" 知道，poj不能%.3lf="" return="" 0;="" }