绝顶我为峰 的妙妙屋

绝顶我为峰 的妙妙屋

海到无边天作岸,山登绝顶我为峰!

题解 P1491 【集合位置 】

posted on 2019-08-12 21:00:14 | under 题解 |

$emm...$这显然是一道次短路模板题,看到大佬们都用的删边法,我这里来一发枚举法吧

我们设有图$G(V,E)$,$e(u,v)$是其中的一条边的,$w(u,v)$是其权值,从$i$到$j$的最短路为$dis[i][j]$,那么从$1$到$n$的次短路可以表示为:

$$\sum_{e(u,v)\in G(v,e)}min(dis[1][u]+w(u,v)+dis[v][n])$$

那么我们只需要枚举每一条边即可,实现预处理最短路,以$1$和$n$为起点分别跑一次,然后算次短路

但是由于这道题要求每个点只能走一次(但是题目并没有说),我们还需要寻找最短路径走向,并且枚举时判断,然后再累加即可

但是这样会超时,我们还需要在判断是加上小优化来节省时间

#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<ext/pb_ds/priority_queue.hpp>
#include<cmath>
#include<cstring>
using namespace std;
using namespace __gnu_pbds;
struct edge
{
    int node;
    double weight;
    edge(int node_,double weight_):
        node(node_),weight(weight_){}
};
vector<edge> v[201];
int n,m,a[201],b[201];
double dis1[201],dis2[201],path1[201],path2[201];
bool vis[201];
inline int read()
{
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9')
    {
        if(c=='-')
            f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=(x<<1)+(x<<3)+c-'0';
        c=getchar();
    }
    return x*f;
}
inline double clac(int a1,int b1,int a2,int b2)
{
    return sqrt((a1-a2)*(a1-a2)+(b1-b2)*(b1-b2));//计算两点距离
}
inline void dijkstra(int s,double dis[])
{
    memset(vis,0,sizeof(vis));
    register __gnu_pbds::priority_queue<pair<double,int>,greater<pair<double,int> >,pairing_heap_tag> q;//平板电视大法好(大雾
    q.push(make_pair(0.00,s));
    while(!q.empty())//板子
    {
        register pair<double,int> k=q.top();
        q.pop();
        if(vis[k.second])
            continue;
        vis[k.second]=1;
        dis[k.second]=k.first;
        for(register vector<edge>::iterator it=v[k.second].begin();it!=v[k.second].end();++it)
            if(!vis[it->node])
                q.push(make_pair(it->weight+k.first,it->node));
    }
}
inline void findway()
{
    for(register int i=1;i<=n;++i)
        for(register vector<edge>::iterator it=v[i].begin();it!=v[i].end();++it)//寻找路径
        {
            //if(!path1[it->node])
                if(dis1[it->node]==dis1[i]+it->weight)
                path1[it->node]=i;
            //if(!path2[it->node])
                if(dis2[it->node]==dis2[i]+it->weight)
                    path2[it->node]=i;
        }
}
inline bool check(int s,int t)
{
    bool qwq[201]={0};
    for(register int i=s,j=t;i||j;i=path1[i],j=path2[j])
        if(qwq[i]||qwq[j])//优化:需要两条路径同时进行判断节省时间
            return 0;
        else
            qwq[i]=qwq[j]=1;
    return 1;
}
int main()
{
    n=read(),m=read();
    for(register int i=1;i<=n;++i)
        a[i]=read(),b[i]=read();
    while(m--)
    {
        register int x=read(),y=read();
        v[x].push_back(edge(y,clac(a[x],b[x],a[y],b[y])));
        v[y].push_back(edge(x,clac(a[x],b[x],a[y],b[y])));
        //cout<<clac(a[x],a[y],b[x],b[y])<<endl;
    }//建图
    dijkstra(1,dis1);//预处理
    dijkstra(n,dis2);
    //cout<<dis1[1]<<" "<<dis1[2]<<" "<<dis1[3]<<" "<<dis2[1]<<" "<<dis2[2]<<" "<<dis2[3]<<endl;
    register double minn=dis1[n],ans=233333333333.00;
    findway();//确定路径
    for(register int i=1;i<=n;++i)
        for(register vector<edge>::iterator it=v[i].begin();it!=v[i].end();++it)//枚举每条边
        {
            register double w=dis1[i]+it->weight+dis2[it->node];
            if(ans==233333333333.00||(w<ans&&w>minn&&check(i,it->node)))//判断是否是次短路并且没有重复经过某个点
                ans=w;//更新答案
        }
    if(ans==233333333333.00)
        puts("-1");
    else
        printf("%.2lf\n",ans);//输出
    return 0;
}