先用floyd 求两点之间的最短距离map[i][j] ,再求各点与牧区内其他结点距离的最大值d[i]。
枚举分别在两个牧区的两个点i,j,
tmp = d[i] + d[j] + ( i, j 之前的距离)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
/**//*
ID: lorelei
TASK: cowtour
LANG: C++
*/
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
#include <fstream>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <memory.h>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
const double INF = 999999.0;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
typedef pair<int, int> PAIR;
PAIR loc[200];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
double map[200][200];
double d[200];
int N;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
inline double dist(int x1, int y1, int x2, int y2)
{
return sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int main()
{
int i,j,k;
double ans= INF;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
ifstream fin("cowtour.in");
ofstream fout("cowtour.out");
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
fin>>N;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for(i=0; i<N; ++i)
fin>>loc[i].first>>loc[i].second;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
char ch;
for(i=0; i<N; ++i)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(j=0; j<N; ++j)
{
fin>>ch;
if(ch=='1')
map[i][j] = map[j][i] = dist(loc[i].first, loc[i].second, loc[j].first, loc[j].second);
else if(ch=='0')
map[i][j] = map[i][j] = INF;
if(i==j)
map[i][j] = 0;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for(k=0; k<N; ++k)
for(i=0; i<N; ++i)
for(j=0; j<N; ++j)
if(map[i][j] > map[i][k]+map[k][j])
map[i][j] = map[i][k]+map[k][j];
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
memset(d, 0, sizeof(d));
for(i=0; i<N; ++i)
for(j=0; j<N; j++)
if(map[i][j]>d[i] && map[i][j]!=INF)
d[i] = map[i][j];
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for(i=0; i<N; ++i)
for(j=0; j<N; ++j)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(map[i][j]==INF)
{
double tmp = d[i]+d[j]+dist(loc[i].first, loc[i].second, loc[j].first, loc[j].second);
if(tmp<ans)
ans = tmp;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for(i=0; i<N; ++i)
if(d[i]>ans)
ans = d[i];
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
fout<<setprecision(6)<<setiosflags(ios::fixed | ios::showpoint)<<ans<<endl;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
return 0;
}
posted on 2010-12-10 19:49
小阮 阅读(183)
评论(0) 编辑 收藏 引用 所属分类:
USACO