P1491 集合位置
2024-08-25 05:44:51
题目描述
每次有大的活动,大家都要在一起“聚一聚”,不管是去好乐迪,还是避风塘,或者汤姆熊,大家都要玩的痛快。还记得心语和花儿在跳舞机上的激情与释放,还记得草草的投篮技艺是如此的高超,还记得狗狗的枪法永远是'S'……还有不能忘了,胖子的歌声永远是让我们惊叫的!!
今天是野猫的生日,所以想到这些也正常,只是因为是上学日,没法一起去玩了。但回忆一下那时的甜蜜总是一种幸福嘛。。。
但是每次集合的时候都会出现问题!野猫是公认的“路盲”,野猫自己心里也很清楚,每次都提前出门,但还是经常迟到,这点让大家很是无奈。后来,野猫在每次出门前,都会向花儿咨询一下路径,根据已知的路径中,总算能按时到了。
现在提出这样的一个问题:给出n个点的坐标,其中第一个为野猫的出发位置,最后一个为大家的集合位置,并给出哪些位置点是相连的。野猫从出发点到达集合点,总会挑一条最近的路走,如果野猫没找到最近的路,他就会走第二近的路。请帮野猫求一下这条第二最短路径长度。
输入输出格式
输入格式:
第一行是两个整数n(1<=n<=200)和m,表示一共有n个点和m条路,以下n行每行两个数xi,yi,(-500<=xi,yi<=500),代表第i个点的坐标,再往下的m行每行两个整数pj,qj,(1<=pj,qj<=n),表示两个点相通。
输出格式:
只有一行包含一个数,为第二最短路线的距离(保留两位小数),如果存在多条第一短路径,则答案就是第一最短路径的长度;如果不存在第二最短路径,输出-1。
输入输出样例
输入样例#1:
3 3
0 0
1 1
0 2
1 2
1 3
2 3
输出样例#1:
2.83
说明
各个测试点1s
Solution:
次短路水题。
数据点很小,所以可以暴力求出最短路,然后枚举删最短路上的边,再求次短路。(其实可以用A*去求k短路的,但是我死活WA两个点,所以就弃疗了)
代码:
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/priority_queue.hpp>
#define il inline
#define ll long long
#define For(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define Bor(i,a,b) for(int (i)=(b);(i)>=(a);(i)--)
using namespace std;
using namespace __gnu_pbds;
const int N=;
int n,m,x[],y[],pre[];
int to[N],net[N],h[],cnt;
double w[N],dis[];
bool ct[][],f;
struct node{
int u;double d;
node(int a=,double b=){u=a,d=b;}
bool operator<(const node &a)const {return d>a.d;}
};
typedef __gnu_pbds::priority_queue<node,less<node>,pairing_heap_tag> heap;
heap q;
heap::point_iterator id[]; il int gi(){
int a=;char x=getchar();bool f=;
while((x<''||x>'')&&x!='-')x=getchar();
if(x=='-')x=getchar(),f=;
while(x>=''&&x<='')a=(a<<)+(a<<)+x-,x=getchar();
return f?-a:a;
} il void add(int u,int v,double c){
to[++cnt]=v,net[cnt]=h[u],w[cnt]=c,h[u]=cnt;
to[++cnt]=u,net[cnt]=h[v],w[cnt]=c,h[v]=cnt;
} il void spfa(){
For(i,,n) dis[i]=,id[i]=;
dis[]=,q.push(node(,));
while(!q.empty()){
node x=q.top();q.pop();
for(int i=h[x.u];i;i=net[i])
if(dis[to[i]]>dis[x.u]+w[i]&&!ct[to[i]][x.u]){
dis[to[i]]=dis[x.u]+w[i];
if(!f)pre[to[i]]=x.u;
if(id[to[i]]==) id[to[i]]=q.push(node(to[i],dis[to[i]]));
else q.modify(id[to[i]],node(to[i],dis[to[i]]));
}
}
} int main(){
n=gi(),m=gi();
For(i,,n) x[i]=gi(),y[i]=gi();
int u,v;
while(m--) u=gi(),v=gi(),add(u,v,sqrt((x[u]-x[v])*(x[u]-x[v])+(y[u]-y[v])*(y[u]-y[v])));
spfa();f=;double ans=;
if(dis[n]==) puts("-1"),exit();
for(int i=n;i!=;i=pre[i]){
ct[pre[i]][i]=ct[i][pre[i]]=;
spfa();
ans=min(ans,dis[n]);
ct[pre[i]][i]=ct[i][pre[i]]=;
}
if(ans==)puts("-1"),exit();
printf("%.2lf",ans);
return ;
}
最新文章
- angular $http 与form表单的select-->;refine
- [Thinking in Java]Nothing but Java
- 阿里云Centos配置iptables防火墙
- 20145303 20145339 《信息安全系统设计基础》 实验五 简单嵌入式WEB服务器实验
- 1.2 认识ASP.NET MVC项目结构
- 实战Django:官方实例Part5
- sed and awk学习笔记
- JS简易时钟
- [Redux] Redux: Extracting Container Components -- AddTodo
- 对于Hadoop的MapReduce编程makefile
- IMCP网际控制协议
- .NET中的repeater简介及分页效果
- nodeJS之路径PATH模块
- 32位linux(centos)下mongoDB的安装
- wordpress配置固定链接nginx访问404问题解决方法
- VB 性能优化点
- jQuery和js之Cookie实现
- iis 发布mvc
- bbs项目中的零碎点记录
- Mongodb集群与分片 1
热门文章
- 优步UBER司机全国各地奖励政策汇总 (2月29日-3月6日)
- mysql 开启远程连接
- 「日常训练」Known Notation(ZOJ-3829)
- hdu1394Minimum Inversion Number(线段树,求最小逆序数)
- Linux命令应用大词典-第12章 程序编译
- [CodeForce455A]Boredom
- 【if控制器】-(某种情况成立就执行的场景)
- Visaul Studio 密钥
- 创新手机游戏《3L》开发点滴(3)——道具、物品、装备表设计 V2(最终版)
- JQuery常用函数方法全集