注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

TsReaper的博客

一起来玩算法竞赛吧~

 
 
 
 
 

日志

 
 

[题解]集合位置  

2015-07-28 19:58:01|  分类: 题解 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
关键字:次短路。

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;
}

  评论这张
 
阅读(3)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018