| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
Dijkstra 改一下松弛条件就好了。//
// 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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator