题解 P1491 【集合位置 】

$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$为起点分别跑一次，然后算次短路 但是由于这道题要求每个点只能走一次（但是题目并没有说），我们还需要寻找最短路径走向，并且枚举时判断，然后再累加即可 但是这样会超时，我们还需要在判断是加上小优化来节省时间 ```cpp #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; } ```