Loading...

洛谷P1491 集合位置

check评论:0 条 remove_red_eye浏览量:517 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2018-10-07

qwq国庆每天都在考试,所以没做啥题

这道题是一个次短路的题目,因为我菜死了不会$A*$所以只能写朴素的算法

因为次短路肯定是和最短路大部分相似,我们只需要枚举删除其中一条边,再依次跑$spfa$救星,这个边,我们只需要记录任意一条最短路中的边即可,我们采用记录被松弛点的前缀$pre$的方式

#include <bits/stdc++.h>
using namespace std;
double dis[210];
int vis[210],head[210],pre[210],x[210],y[210],n,m;
struct edge
{
    int next,to;
    double dis;
}e[10100];
int cnt;
void add(int u,int v,double diss)
{
    cnt++;
    e[cnt].to=v;
    e[cnt].next=head[u];
    head[u]=cnt;
    e[cnt].dis=diss;
}
double getdis(int a,int b,int c,int d)
{
    return sqrt((c-a)*(c-a)+(d-b)*(d-b));
}
void spfa()
{
    queue<int> q;
    memset(vis,0,sizeof(vis));
    fill(dis+1,dis+205,2147483647);
    q.push(1);
    vis[1]=1;
    dis[1]=0;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=head[u];i;i=e[i].next)
        {
            int v=e[i].to;
            if(dis[v]>dis[u]+e[i].dis)
            {
                dis[v]=dis[u]+e[i].dis;
                pre[v]=u;
                if(!vis[v])
                {
                    q.push(v);
                    vis[v]=1;
                }
            }
        }
    }
}
void spfaa(int s=0,int t=0)
{
    queue<int> q;
    memset(vis,0,sizeof(vis));
    fill(dis+1,dis+205,2147483647);
    q.push(1);
    vis[1]=1;
    dis[1]=0;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=head[u];i;i=e[i].next)
        {
            int v=e[i].to;
            if((u==s&&v==t)||(u==t&&v==s))
            {
                continue;
            }
            if(dis[v]>dis[u]+e[i].dis)
            {
                dis[v]=dis[u]+e[i].dis;
                if(!vis[v])
                {
                    q.push(v);
                    vis[v]=1;
                }
            }
        }
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&x[i],&y[i]);
    }
    for(int i=1;i<=m;i++)
    {
        int xx,yy;
        scanf("%d%d",&xx,&yy);
        double mydis=getdis(x[xx],y[xx],x[yy],y[yy]);
        add(xx,yy,mydis);
        add(yy,xx,mydis);
    }
    spfa();
    double pwp=dis[n];
    double las=0x3f3f3f3f;
    int now=n;
    while(now!=1)
    {
        spfaa(pre[now],now);
        double qwq=dis[n];
        now=pre[now];
        if((qwq<las)&&(qwq>pwp))
        {
            las=qwq;
        }
    }
    printf("%.2lf",las);
}

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名