社区讨论

re,help?

P1491集合位置参与者 1已保存回复 1

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@m5582nuw
此快照首次捕获于
2024/12/26 19:10
去年
此快照最后确认于
2025/11/04 12:20
4 个月前
查看原帖
CPP
#include<bits/stdc++.h>
#define map mapp
#define prev prevvvvvvvv
using namespace std;
const int N=400,inf=0x3f3f3f3f;
priority_queue<pair<double,int>,vector<pair<double,int> >,greater<pair<double,int> > >q;
//priority<pair<double,int>,vector<pair<double,int>>,greater<pair<double,int>> >q;
int n,m,x[N+10],y[N+10],t1,t2,to[N+10],nxt[N+10],head[N+10],tot,prev[N+10];//反nxt;
double f[N+10],/*map[N+10][N+10],*/val[N+10],ans=inf*2;
double calc(int a,int b,int c,int d)
{
//	double ret=1.0*sqrt(1.0*(xx-x)*(xx-x)+1.0*(yy-y)*(yy-y));
//	return ret;
	return (double)sqrt(double(a-c)*double(a-c)+double(b-d)*double(b-d));
}
void add(int a,int b)
{
	double z=calc(x[a],y[a],x[b],y[b]);
	to[++tot]=b;
	val[tot]=z;
	nxt[tot]=head[a];
	head[a]=tot;
}
void dijkstra(int a,int b)
{
	for(int i=1;i<=n;i++) f[i]=inf;
	f[1]=0;
//	priority_queue<pair<double,int>,vector<pair<double,int> >,greater<pair<double,int> > >q;
	q.push(make_pair(0,1));
	while(q.size())
	{
		double valu=q.top().first;
		int num=q.top().second;
		q.pop();
		if(valu!=f[num]) continue;
		for(int j=head[num];j;j=nxt[j])
		{
			int v=to[j];
			if((num==a&&v==b)||(num==b&&v==a)) continue;
			//1.主函数已经传入前驱,所以这里可以如此判断,简单思考是否边被删 
			//2.双向图,两种可能
			if(f[v]<=valu+val[j]) continue;
			if(a==-1&&b==-1) prev[v]=num;
			f[v]=valu+val[j];
			q.push(make_pair(f[v],v));
			
		}
		
	}
}
//void add(int a,int b)
//{
//	double z=calc(x[a],y[a],x[b],y[b]);
//	map[x][y]=z;
//}
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++)
	{
		scanf("%d%d",&t1,&t2);
		add(t1,t2);
		add(t2,t1);
	}
	dijkstra(-1,-1); //第一次跑dijk,-1是暗号?
	for(int i=n;i!=1;i=prev[i]) //倒序,问一下老师 
	{
		dijkstra(i,prev[i]);
		ans=min(ans,f[n]);
	}
	if(ans>=inf) puts("-1");  //什么情况会导致无解?? 
	else printf("%.2lf",ans);
}

//1* priority should build in dijkstra  ;;;maybe jokes from writer
//2* prev is what??
//3* maybe not map but val/to/nxt/head
//4* why dijkstra has two number need to add?
//5* dis maybe equals f

回复

1 条回复,欢迎继续交流。

正在加载回复...