# 绝顶我为峰 的妙妙屋

### 题解 P1491 【集合位置 】

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

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

$$\sum_{e(u,v)\in G(v,e)}min(dis[1][u]+w(u,v)+dis[v][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];
{
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()
{
for(register int i=1;i<=n;++i)
while(m--)
{
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;
}