如果你这题 WA on #4 (刚刚发错版了)
查看原帖
如果你这题 WA on #4 (刚刚发错版了)
223392
Belarus楼主2020/6/17 23:31

请在 spfa 或 dijkstra 取出新点并弹出,且修改了 vis 数组的值(仅 spfa)后,判断一下这个点是不是 n ,如果是,请 continue 。
另外,为什么#6老是 WA 啊,有人帮我调一调吗,我感觉各种特判都写了啊,我的输出是 0 ,不知道为什么,这题也没公开数据。
给出一组 Hack 也行啊啊啊啊
附上我的代码:

#include<bits/stdc++.h>
using namespace std;
const int size=50100;
int n,m,s,t,tot=0;
int ver[size],head[size],nxt[size];
double d1[size],d2[size],edge[size],d[size];
int pre1[size],pre2[size];
int v[size];
struct point{
	double x,y;
	inline void input(){cin>>x>>y;}
}p[size];
inline double dis(point x,point y){
	return sqrt((x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y));
}
inline void add(int x,int y,double z){
	ver[++tot]=y;
	edge[tot]=z;
	nxt[tot]=head[x];
	head[x]=tot;
}
inline void spfa(){
	queue<int> q;
	for(int i=0;i<=n+1;++i) d1[i]=d2[i]=1e9;
	memset(v,0,sizeof(v));
	q.push(1);
	d1[1]=0;v[1]=1;
	while(!q.empty()){
		int x=q.front();q.pop();
		v[x]=0;
		if(x==n) continue;
		if(d1[x]>=1e9-1e6) continue;
		for(int i=head[x];i;i=nxt[i]){
			int y=ver[i];
			double z=edge[i];
			if(d1[y]>d1[x]+z){
				d2[y]=d1[y];
				d1[y]=d1[x]+z;
				if(!v[y]) v[y]=1,q.push(y);
			}
			if(d2[y]>d2[x]+z){
				d2[y]=d2[x]+z;
				if(!v[y]) v[y]=1,q.push(y);
			}
			if(d2[y]>d1[x]+z&&d1[y]<d1[x]+z){
				d2[y]=d1[x]+z;
				if(!v[y]) v[y]=1,q.push(y);
			}
		}
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;++i) p[i].input();
	for(int i=1;i<=m;++i){
		int u,v;
		cin>>u>>v;
		if(u==v) continue;
		double w=dis(p[u],p[v]);
		add(u,v,w);
		add(v,u,w);
	}
	spfa();
	if(d2[n]>=1e9-1e-6) cout<<-1;
	else printf("%.2lf\n",d2[n]);
	return 0;
}
2020/6/17 23:31
加载中...