vijos 1069 新年趣事之红包 Prim水题
2024-08-25 21:25:51
描述
xiaomengxian一进门,发现外公、外婆、叔叔、阿姨……都坐在客厅里等着他呢。经过仔细观察,xiaomengxian发现他们所有人正好组成了一个凸多边形。最重要的是,他们每个人手里都拿着一个红包(^o^)。于是非常心急,xiaomengxian决定找一条最短的路线,拿到所有的红包。
假设屋里共有N个人拿着红包,把他们分别从1到N编号。其中,编号为1的人就坐在大门口,xiaomengxian必须从这里出发去拿其它的红包。一条合法的路线必须经过所有的点一次且仅一次。
格式
输入格式
第一行为一个整数N(1<=N<=800)。
以下N行,每行两个实数Xi,Yi,表示该点的坐标。
各个点按照逆时针顺序依次给出。
输出格式
一个实数,表示最短的路线长度(保留三位小数)。
限制
各个测试点1s
题意:给定点的坐标,每个点经过一次问最短路径。
思路:本来想着有什么贪心/数学/DP 方法的,想不出来直接prim水过算了。
/** @Date : 2016-12-14-20.53
* @Author : Lweleth (SoungEarlf@gmail.com)
* @Link : https://github.com/
* @Version :
*/
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
#include <utility>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <stack>
#include <queue>
//#include<bits/stdc++.h>
#define LL long long
#define PII pair<int ,int>
#define MP(x, y) make_pair((x),(y))
#define fi first
#define se second
#define PB(x) push_back((x))
#define MMG(x) memset((x), -1,sizeof(x))
#define MMF(x) memset((x),0,sizeof(x))
#define MMI(x) memset((x), INF, sizeof(x))
using namespace std; const int INF = 0x3f3f3f3f;
const int N = 1e5+20;
const double eps = 1e-8; struct yuu
{
double x, y; }p[1010]; double dis[1010][1010];
bool vis[1010];
int main()
{
int n;
cin >> n;
MMF(vis);
for(int i = 1; i <= n; i++)
{
scanf("%lf%lf", &p[i].x , &p[i].y);
for(int j = 1; j < i; j++)
{
double x = p[i].x - p[j].x;
double y = p[i].y - p[j].y;
dis[i][j] = sqrt(x*x + y*y);
dis[j][i] = dis[i][j];
}
}
double ans = 0;
//prim
for(int i = 0; i < n - 1; i++)
{
double mi = INF;
int pos = -1;
for(int j = 2; j <= n; j++)
{
if(!vis[j] && dis[1][j] < mi)
{
mi = dis[1][j];
pos = j;
}
}
vis[pos] = 1;
//cout << ans << endl;
ans += mi;
for(int j = 2; j <= n; j++)
if(!vis[j] && dis[pos][j] < dis[1][j])
dis[1][j] = dis[pos][j];
}
printf("%.3lf\n", ans);
return 0;
}
最新文章
- 一步一步安装hive
- [转]Golang- import 导入包的语法
- ORA-04031案例一则
- 一致性hash应用到redis
- Helpers\FastCache
- 做一个聪明的.net程序员
- ?Object-C获取手机设备信息
- HDOJ/HDU 2565 放大的X(分段思考~)
- 一款很不错的html转xml工具-Html Agility Pack
- JS 模拟C# 字符串格式化操作
- asp.net mvc使用validate.js验证 若name属性包含特殊字符则加上双引号即可
- ksoap2- webservice
- 编码格式简介:ASCII码、ANSI、GBK、GB2312、GB18030和Unicode、UTF-8,BOM头
- beta冲刺3-咸鱼
- defaultdict使用及__missing__理解
- Dubbo中编码和解码的解析
- Hdoj 1003.Max Sum 题解
- pycharm修改快捷键
- bootstrap学习-初步使用介绍
- 通过实例看懂diff命令输出