「日常训练」「小专题·图论」 Frogger （1-1）

题意

分析

变形的dijkstra。

分析题意之后补充。

代码

// Origin:

// Theme: Graph Theory (Basic)

// Date: 080518

// Author: Sam X

//#include <bits/stdc++.h>

#include <iostream>

#include <utility>

#include <iomanip>

#include <cstring>

#include <cmath>

#define MP make_pair

#define PB push_back

#define fi first

#define se second

#define ZERO(x) memset((x), 0, sizeof(x))

#define ALL(x) (x).begin(),(x).end()

#define rep(i, a, b) for (int i = (a); i <= (b); ++i)

#define per(i, a, b) for (int i = (a); i >= (b); --i)

#define QUICKIO                  \

    ios::sync_with_stdio(false); \

    cin.tie(0);                  \

    cout.tie(0);

using namespace std;

typedef long long ll;

typedef unsigned long long ul;

typedef pair<int,int> pi;

typedef pair<int,pi> pii;

template<typename T>

T read()

{

    T tmp; cin>>tmp;

    return tmp;

}

inline double dist(pi x,pi y) { return sqrt((x.fi-y.fi)*(x.fi-y.fi)+(x.se-y.se)*(x.se-y.se)); }

pi pnt[205];

double d[205][205];

double dijkstra(int cnt,int beg)

{

    bool vis[205]; ZERO(vis);

    double tmpd[205];

    memset(tmpd,0x43,sizeof(tmpd)); // INF

    tmpd[beg]=0;

    rep(i,1,cnt)

    {

        //cout<<endl<<"***"<<endl;

        //rep(i,1,cnt) cout<<tmpd[i]<<" "; cout<<endl;

        int minx=-1;double minv=tmpd[0];

        rep(j,1,cnt) if(!vis[j] && minv-tmpd[j]>1e-8) minv=tmpd[minx=j];

        if(minx==-1) break;

        vis[minx]=true;

        rep(j,1,cnt) if(!vis[j])

        {

            tmpd[j]=min(tmpd[j],max(tmpd[minx],d[minx][j]));

        }

    }

    return tmpd[2];

}

int main()

{

    int n,kase=0;

    while(cin>>n)

    {

        if(!n) break;

        rep(i,1,n)

        {

            cin>>pnt[i].fi>>pnt[i].se;

        }

        rep(i,1,n)

        {

            rep(j,i,n)

            {

                d[i][j]=d[j][i]=dist(pnt[i],pnt[j]);

            }

        }

        cout<<"Scenario #"<<++kase<<endl<<"Frog Distance = "<<fixed<<setprecision(3)<<dijkstra(n,1)<<endl;

        cout<<endl;

    }

    return 0;

}

kuangbin的代码与分析

floyed的算法本身就带有dp的色彩在里面，所以我们可以从这个角度出发分析。

//============================================================================

// Name        : POJ.cpp

// Author      :

// Version     :

// Copyright   : Your copyright notice

// Description : Hello World in C++, Ansi-style

//============================================================================

#include <iostream>

#include <string.h>

#include <stdio.h>

#include <algorithm>

#include <set>

#include <queue>

#include <map>

#include <vector>

#include <string>

#include <math.h>

using namespace std;

const int MAXN=210;

pair<int,int>p[MAXN];

double dis(pair<int,int>p1,pair<int,int>p2)

{

    return sqrt((double)(p1.first-p2.first)*(p1.first-p2.first)+(p2.second-p1.second)*(p2.second-p1.second));

}

double dist[MAXN][MAXN];

int main()

{

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

//    freopen("out.txt","w",stdout);

    int n;

    int x,y;

    int iCase=0;

    while(scanf("%d",&n)==1&&n)

    {

        iCase++;

        printf("Scenario #%d\n",iCase);

        for(int i=0;i<n;i++)

        {

            scanf("%d%d",&x,&y);

            p[i]=make_pair(x,y);

        }

        for(int i=0;i<n;i++)

            for(int j=i;j<n;j++)

            {

                if(i==j)dist[i][j]=dis(p[i],p[j]);

                else dist[j][i]=dist[i][j]=dis(p[i],p[j]);

            }

        for(int k=0;k<n;k++)

            for(int i=0;i<n;i++)

                for(int j=0;j<n;j++)

                    if(dist[i][j]>max(dist[i][k],dist[k][j]))

                        dist[i][j]=max(dist[i][k],dist[k][j]);

        printf("Frog Distance = %.3f\n\n",dist[0][1]);

    }

    return 0;

}