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

Dijkstra 改一下松弛条件就好了。

Posted by GoZY at 2016-06-04 09:46:44 on Problem 2253
//
//  main.cpp
//  poj 2253
//
//  Created by  on 16/6/4.
//  Copyright © 2016年 . All rights reserved.
//  注意sqrt里面不支持int类型,改成double以防RE

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
int n,x[210],y[210];
double g[210][210];
double dij(int u,int v)
{
    int i,j,k;
    bool b[210];
    double h,zmin,dist[210];
    memset(b,true,sizeof(b));
    
    for (i = 1; i <= n; ++i)
    {
        dist[i] = g[u][i];
        b[i] = true;
    }
    dist[u] = 0;
    b[u] = false;
    for (i = 1; i < n; ++i)
    {
        zmin = 99999999;
        for (j = 1; j <= n; ++j)
        if (b[j]&&dist[j]<zmin)
        {
            zmin = dist[j];
            k = j;
        }
        b[k] = false;
        for (j = 1; j <= n; ++j)
        {
            h = max(dist[k],g[k][j]);
            dist[j] = min(dist[j],h);
        }
    }
    return dist[2];
}
int main(int argc, const char * argv[]) {
    int i,j,k,p;
    p = 0;
    while (cin >> n)
    {
        p++;
        memset(g,0,sizeof(g));
        if (n == 0)
            break;
        for (i = 1; i <= n; ++i)
        {
            scanf("%d%d",&x[i],&y[i]);
        }
        for (i = 1; i <= n; ++i)
        {
            for (j = 1; j <= n; ++j)
                if (i==j)
                    g[i][i] = 0;
                else
                    g[i][j] = sqrt(1.0*(x[i]-x[j])*(x[i]-x[j])+1.0*(y[i]-y[j])*(y[i]-y[j]));
        }
        printf("Scenario #%d\n",p);
        printf("Frog Distance = %.3f\n",dij(1,2));
        puts("");
    }
    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