AC日记——集合位置 洛谷 P1491

集合位置

思路：

　　次短路；

　　先走一遍最短路；

　　记录最短路径，然后依次删边走最短路；

　　最短的长度就是次短路；

来，上代码：

#include <queue>

#include <cmath>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

#define INF 0x7ffffff

struct EdgeType {

    int v,e;

    double w;

};

struct EdgeType edge[];

struct PointType {

    int x,y;

};

struct PointType node[];

int n,m,head[],cnt=,pre[],tot,uu[],vv[];

double dis[],shorest=INF,ans=INF;

bool if_[];

inline void in(int &now)

{

    int if_z=;now=;

    char Cget=getchar();

    while(Cget>''||Cget<'')

    {

        if(Cget=='-') if_z=-;

        Cget=getchar();

    }

    while(Cget>=''&&Cget<='')

    {

        now=now*+Cget-'';

        Cget=getchar();

    }

    now*=if_z;

}

inline double d(int u,int v)

{

    double xx=node[u].x-node[v].x;

    double yy=node[u].y-node[v].y;

    return sqrt(xx*xx+yy*yy);

}

inline void edge_add(int u,int v,double w)

{

    edge[++cnt].e=head[u],head[u]=cnt,edge[cnt].v=v,edge[cnt].w=w;

    edge[++cnt].e=head[v],head[v]=cnt,edge[cnt].v=u,edge[cnt].w=w;

}

void spfa(int pu,int pv)

{

    for(int i=;i<=n;i++) dis[i]=INF,if_[i]=false,pre[i]=-;

    queue<int>que;que.push(),dis[]=,if_[]=true;

    while(!que.empty())

    {

        int now=que.front();que.pop(),if_[now]=false;

        for(int i=head[now];i;i=edge[i].e)

        {

            if((now==pu&&edge[i].v==pv)||(now==pv&&edge[i].v==pu)) continue;

            if(dis[edge[i].v]>dis[now]+edge[i].w)

            {

                pre[edge[i].v]=i;

                dis[edge[i].v]=dis[now]+edge[i].w;

                if(!if_[edge[i].v])

                {

                    que.push(edge[i].v);

                    if_[edge[i].v]=true;

                }

            }

        }

    }

}

int main()

{

    in(n),in(m);int u,v;

    for(int i=;i<=n;i++) in(node[i].x),in(node[i].y);

    for(int i=;i<=m;i++)

    {

        in(u),in(v);

        edge_add(u,v,d(u,v));

    }

    spfa(,),shorest=dis[n];

    if(shorest==INF)

    {

        printf("-1");

        return ;

    }

    int now=n;

    while(pre[now]!=-)

    {

        tot++;

        vv[tot]=edge[pre[now]].v;

        uu[tot]=edge[pre[now]^].v;

        now=edge[pre[now]^].v;

    }

    for(int i=;i<=tot;i++)

    {

        spfa(uu[i],vv[i]);

        ans=min(ans,dis[n]);

    }

    if(ans!=INF) printf("%.2f\n",ans);

    else printf("-1\n");

    return ;

}