不经过重复点的最短路【迷阵突围】

本文主要是介绍不经过重复点的最短路【迷阵突围】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意

在这里插入图片描述

思路

跑最短路，记录前驱
把最短的边删去一条，比较次短路
记得初使化！！！！！多次用到st数组

#include<iostream>
#include<algorithm>
#include<string.h>
#include<cmath>
using namespace std;
typedef pair<int,int>pll;
const double INF=1e18;
const int N=220;
int n,m;
pll P[N];
double w[N][N],dis[N],dis_t[N];
bool st[N];
double get_pos(int a,int b)
{double dx=P[a].first-P[b].first;double dy=P[a].second-P[b].second;return sqrt(dx*dx+dy*dy);
}
int  pre[N];
int pre_p[N];
void dijistra()
{for(int i=1;i<=n;i++) st[i]=0;for(int i=1;i<=n;i++) dis[i]=INF;memset(pre,-1,sizeof pre);dis[1]=0;for(int i=1;i<=n;i++){int t=-1;for(int j=1;j<=n;j++)if(!st[j] && (t==-1||dis[t]>dis[j]))t=j;st[t]=1;for(int j=1;j<=n;j++){if(dis[j]>dis[t]+w[t][j]){dis[j]=dis[t]+w[t][j];pre[j]=t;}}}
}
int main()
{cin>>n>>m;for(int i=1;i<=n;i++){int x,y;cin>>x>>y;P[i]={x,y};}for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)w[i][j]=INF;//for(int i=1;i<=n;i++) w[i][i]=0;for(int i=1;i<=m;i++){int a,b;cin>>a>>b;double distance=get_pos(a,b);w[a][b]=w[b][a]=min(w[a][b],distance);}dijistra();if(dis[n]==INF) {cout<<"-1"<<endl;return 0;}double zdlu=dis[n];memcpy(pre_p,pre,sizeof pre);double res=INF;int tt=n;while(pre_p[tt]!=-1){int b=tt,a=pre_p[b];//cout<<a<<"  "<<b<<endl;w[a][b]=w[b][a]=INF;dijistra();// for(int i=1;i<=n;i++)//    cout<<dis[i]<<endl;double cdlu=dis[n];//cout<<"res=="<<res<<endl;res=min(res,cdlu);w[a][b]=w[b][a]=get_pos(a,b);tt=pre_p[tt];//cout<<"tt=="<<tt<<endl;}if(res==INF) {cout<<"-1"<<endl;return 0;}printf("%.2lf\n",res);return 0;
}