POJ-2253最短

タイトルリンク:http://poj.org/bbs?problem_id=2253題意:A点からB点にジャンプするカエルがいます.カエルは体の機能が制限されているので、限界ジャンプの遠さがあります.求:この限界は少なくともいくらで、この任務を完成することができます.点は2 D座標で、最初の点はA点、2番目の点はB点です.規模:n(2<=n<=200).(0<=xi,yi<=1000)タイプ:最短
分析:緩和条件を修正し、dist[]が最短ルートを記録するのではなく、この道の最大costを記録する.すなわちif(minimax[v]>max(minimax[u],cost))minimax[v]=max(minimax[u],cost);
最後に、気をつけて!!(「%.3 lf」はwa,「%.3 f」になります).mdzz. 時間複雑度&&最適化:O(n*n)コード:

#include
#include
#include
#include
#include
#include
#include
#include
#include

using namespace std;

const int INF = 1000000007;
const int MAXN=2005;
const int MAXM=10005;

struct Edge{
    int v;
    double cost;
    Edge(int _v=0,double _cost=0):v(_v),cost(_cost){}
};

vector edge[MAXN];

void init(){
    for(int i=0;ivoid add_edge(int a,int b,double cost){
    edge[a].push_back(Edge(b,cost));
}

double minimax[MAXN];
int vis[MAXN];
int cnt[MAXN];
bool SPFA(int n,int start){
    for(int i=0;i<=n;i++){
        minimax[i]=INF;
    }
    memset(vis,0,sizeof(vis));
    memset(cnt,0,sizeof(cnt));
    queue<int> q;
    while(!q.empty())q.pop();
    q.push(start);
    minimax[start]=0;
    cnt[start]=1;vis[start]=1;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        vis[u]=0;
        //cout<
        for(int i=0;iint v=edge[u][i].v;
            double cost=edge[u][i].cost;
            if(minimax[v]>max(minimax[u],cost)){
                minimax[v]=max(minimax[u],cost);
                if(!vis[v]){
                    vis[v]=true;
                    q.push(v);
                    if(++cnt[v]>n)return false;
                }
            }
        }
    }
    return true;
}

int n,m;
struct node{
    int x,y;
    node(int _x=0,int _y=0):x(_x),y(_y){}
};

node p[MAXN];

int main()
{
    int kase=1;
    while(cin>>n&&n!=0){
        init();
        for(int i=0;iint a,b;
            cin>>a>>b;
            p[i]=node(a,b);
        }
        for(int i=0;ifor(int j=i+1;jdouble cost=(double)( (p[i].x-p[j].x)*(p[i].x-p[j].x)+(p[i].y-p[j].y)*(p[i].y-p[j].y) );
                cost=sqrt(cost);
                add_edge(i,j,cost);
                add_edge(j,i,cost);
            }
        }
//        for(int i=0;i
//            for(int j=0;j
//                cout<
//            }cout<
//        }
        SPFA(n,0);
        printf("Scenario #%d
Frog Distance = %.3f

",kase++,minimax[1]);
    }
    return 0;
}