社区讨论
为什么不对
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 条回复,欢迎继续交流。
正在加载回复...