Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

楼上为何说不是最短路呢,不解,我是来贴代码的

Posted by speedcell4 at 2011-09-06 23:56:35 on Problem 2253
#include<iostream>
#include<queue>
#include<cmath>

using namespace std;

#define SIZE 100000
#define More(x,y) ((x-y)>1e-8)
#define Less(x,y) ((y-x)>1e-8)
#define Equl(x,y) (fabs(x-y)<1e-8)
#define Maxn(x,y) (More((x),(y))?(x):(y))

int times=1;
int t,n;
int x,y,z;
int c[500][500];
double dist[SIZE];
bool inqueue[SIZE];

struct node
{
    int v;
    double w;
}edge[SIZE];
int index,pre[SIZE],next[SIZE];

void clear(void)
{
    index=0;
    memset(pre,-1,sizeof(pre));
    memset(next,-1,sizeof(next));
}
void add(int u,int v,double w)
{
    edge[index].v=v;
    edge[index].w=w;
    next[index]=pre[u];
    pre[u]=index++;
}

queue<int> open;

void Init(int s)
{
    memset(dist,0x7f,sizeof(dist));
    memset(inqueue,false,sizeof(inqueue));
    dist[s]=0;
    open.push(s);
}
void SPFA(int s)
{
    Init(s);
    while(!open.empty())
    {
        int u=open.front(); open.pop(); inqueue[u]=false;
        for(int i=pre[u];i!=-1;i=next[i])
        {
            int v=edge[i].v;
            double w=edge[i].w;
            if(More(dist[v],Maxn(w,dist[u])))
            {
                dist[v]=Maxn(w,dist[u]);
                if(!inqueue[v])
                {
                    inqueue[v]=true;
                    open.push(v);
                }
            }
        }
    }
}
double findAns(void)
{
    SPFA(0);
    return dist[1];
}
int main()
{
    while(scanf("%d",&n),n)
    {
        clear();
        for(int i=0;n-i>0;i++)
        {
            scanf("%d %d",&x,&y);
            c[i][0]=x;
            c[i][1]=y;
            for(int j=0;i-j>0;j++)
            {
                double len=sqrt((c[j][0]-c[i][0])*1.0*(c[j][0]-c[i][0])+(c[j][1]-c[i][1])*1.0*(c[j][1]-c[i][1]));
                add(i,j,len);
                add(j,i,len);
            }
        }
        printf("Scenario #%d\n",times++);
        printf("Frog Distance = %.3lf\n\n",findAns());
    }
    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator