洛谷P1491集合位置

传送门啦

这个题说白了就是求一个次短路。

方法是我们先跑一遍最短路，记录下最短路上每一个点的前驱。然后我们将最短路上每一条边都标记一次，分别跑一边最短路，求出最短路径即可。

在这我们不用特殊判断是否是第二条次短路还是最短路。因为我们求出的 $ ans $ 是一个最小值。

#include <cstdio>

#include <iostream>

#include <algorithm>

#include <cstring>

#include <vector>

#include <stack>

#include <queue>

#include <cmath>

#define INF 0x3f3f3f3f

using namespace std;

const int maxn = 510;

const int maxm = 500010;

int head[maxn],tot;

double dis[maxn];

bool vis[maxn];

double ans = INF;

int n,m;

int x[maxn],y[maxn],pre[maxn];

struct Edge{

	int from,to,next;

	double val;

}edge[maxm << 1];

inline double num(int i,int j){

	int xx = x[i] - x[j];

	int yy = y[i] - y[j];

	return sqrt(xx * xx + yy * yy);

}

inline void add(int u,int v,double w){

	edge[++tot].from = u;

	edge[tot].to = v;

	edge[tot].val = w;

	edge[tot].next = head[u];

	head[u] = tot;

}

inline void spfa(int aa,int bb){

	for(int i=1;i<=n;i++)  dis[i] = INF;

	queue<int> q;

	memset(vis , false , sizeof(vis));

	q.push(1);

	vis[1] = true;

	dis[1] = 0;

	while(!q.empty()){

		int cur = q.front();

		q.pop();

		vis[cur] = false;

		for(int i=head[cur];i;i=edge[i].next){

			int v = edge[i].to;

			if((cur == aa) && (v == bb) || (cur == bb) && (v == aa)) continue;

			if(dis[v] > dis[cur] + edge[i].val){

				dis[v] = dis[cur] + edge[i].val;

				if(aa == -1 && bb == -1)

					pre[v] = cur;

				if(!vis[v]){

					vis[v] = true;

					q.push(v);

				}

			}

		}

	}

}

int main(){

	scanf("%d %d",&n,&m);

	for(int i=1;i<=n;i++){

		scanf("%d %d",&x[i],&y[i]);

	}

	for(int i=1;i<=m;i++){

		int x,y;

		scanf("%d %d",&x,&y);

		double z = num(x , y);

		add(x , y , z);

		add(y , x , z);

	}

	spfa(-1 , -1);

	for(int i=n;pre[i];i=pre[i]){

		spfa(pre[i] , i);

		ans = min(ans , dis[n]);

	}

	if(ans == INF)  printf("-1\n");

	else printf("%.2lf",ans);

	return 0;

}