8
16
2015
0

[题解]集合位置

关键字:次短路。

Link&Limit


[洛谷1491]

时间限制: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;
}
Category: 题解 | Tags: 图论 最短路 洛谷 | Read Count: 527

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

| Theme: Aeros 2.0 by TheBuckmaker.com