洛谷 P1491 集合位置

题目描述

每次有大的活动，大家都要在一起“聚一聚”，不管是去好乐迪，还是避风塘，或者汤姆熊，大家都要玩的痛快。还记得心语和花儿在跳舞机上的激情与释放，还记得草草的投篮技艺是如此的高超，还记得狗狗的枪法永远是'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：

输出样例#1：

2.83

说明

各个测试点1s

一句话题意：给你一个有n个点的平面坐标系，某些点之间有边，要求第1个点到第n个点的次短路。

这是一道k短路的模板题，但是由于本人太弱了，并不会k短路........

所以我们可以想一些比较巧的算法。

这道题是次短路，而最短路我们是很容易求出来的，我们可以尝试一下在最短路上处理来做这道题。

既然不能走和最短路完全一样的边，那么我们每次把最短路上的一条边删去，再跑spfa或者dijkstra，跑的次数取决于最短路经过几条边。

要找到最短路的边的话，需要记录前驱。每次进行松弛操作的时候如果dis被更新了，就记录前驱。(思考一下应该就能明白为什么不能记录后驱)。

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 int read()//快读
  4 {
  5     int x=0,w=1;char ch=getchar();
  6     while(ch>'9'||ch<'0') {if(ch=='-')w=-1;ch=getchar();}
  7     while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
  8     return x*w;
  9 }
 10 int cnt;
 11 int x[210],y[210],head[210],vis[210],team[500010],from[210],bian[210],s[500010];
 12 double dis[210];//注意开double
 13 struct node{
 14 int to,next;double v;
 15 }edge[500010];
 16 void add(int a,int b)
 17 {
 18     cnt++;
 19     edge[cnt].to=b;
 20     edge[cnt].next=head[a];
 21     edge[cnt].v=sqrt((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]));
 22     head[a]=cnt;
 23 }
 24 void spfa()
 25 {
 26     memset(dis,127,sizeof(dis));
 27     int l=0,r=1,u,v;
 28     team[1]=1;vis[1]=1;dis[1]=0;
 29     while(l<r)
 30     {
 31         l++;
 32         u=team[l];
 33         vis[u]=0;
 34         for(int i=head[u];i;i=edge[i].next)
 35         {
 36             v=edge[i].to;
 37             if(dis[v]>dis[u]+edge[i].v)
 38             {
 39                 dis[v]=dis[u]+edge[i].v;
 40                 from[v]=u;//记录前驱
 41                 if(!vis[v])
 42                 {
 43                     vis[v]=1;
 44                     r++;
 45                     team[r]=v;
 46                 }
 47             }
 48         }
 49     }
 50 }
 51 void spfa2(int x,int y)//这里注意是要分spfa和spfa2的，因为第一次要记录前驱节点。而后几次如果仍然记录的话接下来的递归就会出柜了！！！具体看写法，也可以第一次spfa后直接递归把边用数组存起来，这样就不必要分开写两个。
 52 {
 53     memset(dis,127,sizeof(dis));
 54     int l=0,r=1,u,v;
 55     team[1]=1;vis[1]=1;dis[1]=0;
 56     while(l<r)
 57     {
 58         l++;
 59         u=team[l];
 60         vis[u]=0;
 61         for(int i=head[u];i;i=edge[i].next)
 62         {
 63             v=edge[i].to;
 64             if((v==y&&u==x)||(v==x&&u==y)) continue;
 65             if(dis[v]>dis[u]+edge[i].v)
 66             {
 67                 dis[v]=dis[u]+edge[i].v;
 68                 if(!vis[v])
 69                 {
 70                     vis[v]=1;
 71                     r++;
 72                     team[r]=v;
 73                 }
 74             }
 75         }
 76     }
 77 }
 78 int main()
 79 {
 80     int n,m,xi,yi;
 81     double minn=90000000;
 82     n=read();m=read();
 83     for(int i=1;i<=n;i++)
 84     {
 85         x[i]=read();y[i]=read();
 86     }
 87     for(int i=1;i<=m;i++)
 88     {
 89         xi=read();yi=read();
 90         add(xi,yi);
 91         add(yi,xi);
 92     }
 93     spfa();
 94     int v=n;
 95     double tmp;
 96     while(v!=1)
 97     {
 98         spfa2(v,from[v]);
 99         if(dis[n]<minn) minn=dis[n];
100         v=from[v];
101     }
102     if(minn==90000000)
103     {
104         printf("-1");
105         return 0;
106     }
107     else
108     printf("%.2lf
",minn);
109 }

View Code