关键字：次短路。
Link&Limit
时间限制：1000ms 空间限制：131072kb
Description
每次有大的活动，大家都要在一起“聚一聚”，不管是去好乐迪，还是避风塘，或者汤姆熊，大家都要玩的痛快。还记得心语和花儿在跳舞机上的激情与释放，还记得草草的投篮技艺是如此的高超，还记得狗狗的枪法永远是'S'……还有不能忘了，胖子的歌声永远是让我们惊叫的！！
今天是野猫的生日，所以想到这些也正常，只是因为是上学日，没法一起去玩了。但回忆一下那时的甜蜜总是一种幸福嘛。。。
但是每次集合的时候都会出现问题！野猫是公认的“路盲”，野猫自己心里也很清楚，每次都提前出门，但还是经常迟到，这点让大家很是无奈。后来，野猫在每次出门前，都会向花儿咨询一下路径，根据已知的路径中，总算能按时到了。
现在提出这样的一个问题：给出n个点的坐标，其中第一个为野猫的出发位置，最后一个为大家的集合位置，并给出哪些位置点是相连的。野猫从出发点到达集合点，总会挑一条最近的路走，如果野猫没找到最近的路，他就会走第二近的路。请帮野猫求一下这条第二最短路径长度。
Input Format
第一行是两个整数n和m，表示一共有n个点和m条路，以下n行每行两个数xi，yi，代表第i个点的坐标，再往下的m行每行两个整数pj，qj(1 ≤ pj,qj ≤ n)，表示两个点相通。
Output Format
只有一行包含一个数，为第二最短路线的距离（保留两位小数），如果存在多条第一短路径，则答案就是第一最短路径的长度；如果不存在第二最短路径，输出－1。
Sample Input #1
3 3
0 0
1 1
0 2
1 2
1 3
2 3
Sample Output #1
2.83
Hint
对于100%的数据，1 ≤ n ≤ 200，-500 ≤ xi,yi ≤ 500.
次短路模版题。首先找出一条最短路，之后一次去掉一条最短路上的边，对于每一次去掉一条边后的图都跑一次最短路，其中最小的答案就是次短路。
为什么要去掉最短路上的一条边呢？因为次短路和最短路必然至少有一条边不是共有的。为什么不去掉不在最短路上的边呢？因为这样最短路是没有变化的。
#include <stdio.h>
#include <string.h>
#include <math.h>
#define QLEN 205
int n,m,x[210],y[210];
int e[80010][2],p[210];
int q[210],from[210],head,tail;
double v[80010],dis[210],ans = 999999999;
short vis[210];
double min(double a,double b)
{
return a<b?a:b;
}
void adde(int sn,int fn,double val,int id)
{
e[id][0] = fn; v[id] = val; e[id][1] = p[sn]; p[sn] = id;
e[id+1][0] = sn; v[id+1] = val; e[id+1][1] = p[fn]; p[fn] = id+1;
}
void spfa(int ban,short mode)
{
int i,sn,fn;
memset(dis,127,sizeof(dis));
head = 1; tail = 2;
q[1] = 1; vis[1] = 1; dis[1] = 0;
while(head != tail)
{
sn = q[head++];
for(i=p[sn];i;i=e[i][1])
{
if(i == ban || i == (ban^1)) continue;
fn = e[i][0];
if(dis[fn]>dis[sn]+v[i])
{
dis[fn] = dis[sn]+v[i];
if(mode) from[fn] = (i^1);
if(vis[fn]) continue;
vis[fn] = 1; q[tail++] = fn;
if(tail>QLEN) tail = 1;
}
}
vis[sn] = 0;
if(head>QLEN) head = 1;
}
}
int main()
{
int i,sn,fn;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++) scanf("%d%d",&x[i],&y[i]);
for(i=1;i<=m;i++)
{
scanf("%d%d",&sn,&fn);
adde(sn,fn,sqrt((x[sn]-x[fn])*(x[sn]-x[fn])+(y[sn]-y[fn])*(y[sn]-y[fn])),i<<1);
}
spfa(0,1);
for(sn=n;sn!=1;sn=e[from[sn]][0])
{
spfa(from[sn],0);
ans = min(ans,dis[n]);
}
if(ans < 99999999) printf("%.2f",ans);
else printf("-1");
return 0;
}
评论 (0)
