lg1491

链接:lg1491

Description

  • 每次有大的活动,大家都要在一起“聚一聚”,不管是去好乐迪,还是避风塘,或者汤姆熊,大家都要玩的痛快。还记得心语和花儿在跳舞
  • 机上的激情与释放,还记得草草的投篮技艺是如此的高超,还记得狗狗的枪法永远是’S’……还有不能忘了,胖子的歌声永远是让我们惊叫
  • 的!!
  • 今天是野猫的生日,所以想到这些也正常,只是因为是上学日,没法一起去玩了。但回忆一下那时的甜蜜总是一种幸福嘛。。。
  • 但是每次集合的时候都会出现问题!野猫是公认的“路盲”,野猫自己心里也很清楚,每次都提前出门,但还是经常迟到,这点让大家很是
  • 无奈。后来,野猫在每次出门前,都会向花儿咨询一下路径,根据已知的路径中,总算能按时到了。
  • 现在提出这样的一个问题:给出n个点的坐标,其中第一个为野猫的出发位置,最后一个为大家的集合位置,并给出哪些位置点是相连
  • 的。野猫从出发点到达集合点,总会挑一条最近的路走,如果野猫没找到最近的路,他就会走第二近的路。请帮野猫求一下这条第二最短
  • 路径长度。

    Input

  • 第一行是两个整数n(1<=n<=200)和m,表示一共有n个点和m条路,以下n行每行两个数xi,yi,(-500<=xi,yi<=500),代表第i个点的坐
  • 标,再往下的m行每行两个整数pj,qj,(1<=pj,qj<=n),表示两个点相通。

    Output

  • 只有一行包含一个数,为第二最短路线的距离(保留两位小数),如果存在多条第一短路径,则答案就是第一最短路径的长度;如果不存
  • 在第二最短路径,输出-1。

    Sample Input

    3 3
    0 0
    1 1
    0 2
    1 2
    1 3
    2 3

    Sample Output

    2.83

    题解

  • 求次短路,只需要把最长路求出来记录路劲,然后所有第二短路求最小值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<cstring>
#include<algorithm>
#define rep(i,x,y) for(register int i=x;i<=y;++i)
#define repd(i,x,y) for(register int i=x;i>=y;--i)
#define ll long long
using namespace std;
typedef pair<double,int> l;
const int N=507;
int pre[N],head[N],in[N],n,m,x[N],y[N],cnt;
double dis[N],g[N][N],tp[N];
priority_queue<l,vector<l>,greater<l> >q;
double len(int a,int b){
return sqrt(pow(x[a]-x[b],2)+pow(y[a]-y[b],2));
}

double dijkstra(int s,int t,int op){
while(!q.empty())q.pop();
rep(i,1,n)dis[i]=0x3f3f3f3f;
memset(in,0,sizeof(in));
q.push(l(0,s));
dis[s]=0;
while(!q.empty()){
int k=q.top().second;
q.pop();
in[k]=1;
rep(i,1,n){
if(dis[k]+g[k][i]>=dis[i])continue;
dis[i]=dis[k]+g[k][i];
if(op)pre[i]=k;
if(!in[i])q.push(l(dis[i],i));
}
}
return dis[t]==0x3f3f3f3f?-1:dis[t];
}

int main(){
scanf("%d%d",&n,&m);
rep(i,1,n)scanf("%d%d",&x[i],&y[i]);
rep(i,1,n)rep(j,1,n)if(i!=j)g[i][j]=0x3f3f3f3f;
rep(i,1,m){
int a,b,c;
scanf("%d%d",&a,&b);
g[a][b]=g[b][a]=len(a,b);
}
if(dijkstra(1,n,1)==-1)printf("-1\n");
else {
for(int i=n;i!=1;i=pre[i]){
double k=g[i][pre[i]];
g[i][pre[i]]=g[pre[i]][i]=0x3f3f3f3f;
tp[cnt++]=dijkstra(1,n,0);
g[i][pre[i]]=g[pre[i]][i]=k;
}
double ans=0x3f3f3f3f;
rep(i,0,cnt-1)if(tp[i]!=-1)ans=min(ans,tp[i]);
printf("%.2lf\n",ans);
}
return 0;
}