社区讨论

为什么不对

P1907设计道路参与者 1已保存回复 0

讨论操作

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

当前回复
0 条
当前快照
1 份
快照标识符
@lo965cfh
此快照首次捕获于
2023/10/28 06:12
2 年前
此快照最后确认于
2023/10/28 06:12
2 年前
查看原帖
CPP
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <cmath>
#pragma GCC optimize ("2")
using namespace std;
struct edge {
  int to;
  double w;	//to下一个点,w边权值 
};
double g[1004][1004];
double TU, SH;
int n;
double sx, sy, ex, ey;
double dis[20005];	//dis[i]存到i点的最短路径 
bool found[20005], vis[1004][1004];	//found[i]记录第i个点最短路径是否确定 
void Dijkstra(int st)	//原点为st,dijkstra算最短路径 
{
	memset(dis, 0x3f, sizeof(dis));	//先把所有点的最短路径初始化无穷大
	dis[st]=0;//原点的最短路径置为1
	while(true)//不断重复以下过程,直到所有点变为蓝点
	{
		int u=-1;
		double minn=0x3f3f3f3f;
		//每次找到左右白点中路径值最小的点
		for(int i=1; i<=n; i++)
			if(!found[i] && (u==-1||dis[i]<dis[u]))
				u=i;
		if(u==-1)
			break;
		found[u]=true;	//变为蓝点
		//从这个点出发,对它出边的点进行松弛操作 
		for(int i=0; i<n+2; i++)
		{
			double e=g[u][i];
			if(!found[i])
				dis[i]=min(dis[i], dis[u]+g[u][i]);
		}
	}
}
double diser(double xx1,double yx1, double xx2, double yx2)
{
	return sqrt((xx1-xx2)*(xx1-xx2)+(yx1-yx2)*(yx1-yx2));
}
double x[1001], y[1001];
int main()
{
	cin >> TU >>SH;
	cin >>n;
	for(int i=1; i<=n; i++)
		cin >> x[i] >>y[i];
	int t, w;
	while(cin >>t>>w&&t!=0 &&w!=0)
	{
		vis[t][w]=vis[w][t]=true;
		g[t][w]=g[w][t] = SH*diser(x[t],y[t],x[w],y[w]);
	}
	cin >> sx >>sy >> ex >> ey;
	x[0]=sx, y[0]=sy, x[n+1]=ex, y[n+1]=ey;
	for(int i=0; i<=n+1; i++)
		for(int j=0; j<=n+1; j++)
			if(!vis[i][j])
				g[i][j]=g[j][i]=TU*diser(x[i], y[i], x[j], y[j]);
	Dijkstra(0);
	printf("%.4f",dis[n+1]);
	return 0;
}

回复

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

正在加载回复...