WA #3 #4 #6

大概思路是建最短路然后枚举每条边打擂台更新答案。

#include <bits/stdc++.h>
using namespace std;
typedef double dd;
typedef pair<double,double> PDD;
typedef pair<double,int> PII;
#define x_ first
#define y_ second

double Dis(PDD a,PDD b)
{
	return sqrt((a.x_-b.x_)*(a.x_-b.x_)+(a.y_-b.y_)*(a.y_-b.y_));
}

const int N=610,M=1e5+10;

int n,m;
PDD pos[N];
struct EDGE
{
	int u,v; dd w;
} E[M];
int head[N],ver[M],nxt[M],tot=0,ind[N]; dd edg[M];
void add(int x,int y,dd w)
{
	ver[++tot]=y; nxt[tot]=head[x]; head[x]=tot; edg[tot]=w;
}
dd diss[N],dist[N];
bool vis[N];
priority_queue<PII,vector<PII>,greater<PII>> q;

void dij(int s,dd dis[])
{
	memset(vis,0,sizeof vis);
	memset(dis,127,sizeof diss);
	dis[s]=0; q.push({0,s});
	while(q.size())
	{
		int x=q.top().y_;
		q.pop();
		if(vis[x]) continue;
		vis[x]=1;
		for(int i=head[x];i;i=nxt[i])
		{
			int y=ver[i];
			if(dis[y]>dis[x]+edg[i])
			{
				dis[y]=dis[x]+edg[i];
				q.push({dis[y],y});
			}
		}
	}
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%lf%lf",&pos[i].x_,&pos[i].y_);
	for(int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		dd w=Dis(pos[x],pos[y]);
		add(x,y,w); add(y,x,w);
		E[i]=(EDGE){x,y,w};
	}
	dij(1,diss); dij(n,dist);
	dd minn=4e6+10;
	int tms=0;
	for(int i=1;i<=m;i++)
	{
		int u=E[i].u,v=E[i].v; dd w=E[i].w;
		if(diss[u]+dist[v]>diss[v]+dist[u]) swap(u,v);
		if(diss[u]+w+dist[v]==diss[n]) ind[v]++;
		if(ind[v]>=2) 
		{
			minn=diss[n];
			break;
		}
		if(diss[u]+w+dist[v]>diss[n]) minn=min(diss[u]+w+dist[v],minn);
	}
	if(minn==4e6+10) printf("-1");
	else printf("%.2lf",minn);
	return 0;
}