自动搬运

查看原文

来自洛谷，原作者为

	wwwidk1234 不拿普及组一等奖不改签名 | 最后在线时间：2025年8月23日2时54分

搬运于2025-08-24 21:31:46，当前版本为作者最后更新于2023-08-15 22:15:29，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门

也许更好的阅读体验？

前置芝士

• 链式前向星储存图。

• Dijkstra 算法。

• 欧几里得距离。

题目分析

这是一道最短路题，可以把 $0$ 号点当做码头，把 $n+1$ 号点当做家，最后从 $0$ 号点跑一遍 Dijkstra，设 $distanc_i$ 表示从起点 $0$ 到点 $i$ 的最短距离，那么 $distanc_{n+1}$ 即为本题答案。

建图方式

考虑使用链式前向星储存图，每条边的权重为对应的距离乘对应的不满值。以下是欧几里得距离的计算公式：

先建立 Rome Road，再建立 Dirt Road，详见代码：

cin>>dirt>>rome;
cin>>n;
for(int i=1;i<=n;i++)
	cin>>posx[i]>>posy[i];
while(1)
{
	int x,y;
	cin>>x>>y;
	if(x==0&&y==0) break;
	vis1[x][y]=vis1[y][x]=true;
	double res=dis(posx[x],posx[y],posy[x],posy[y]);
	addEdge(x,y,rome*res);
	addEdge(y,x,rome*res);
}
cin>>posx[0]>>posy[0]>>posx[n+1]>>posy[n+1];
for(int i=0;i<=n+1;i++)
	for(int j=0;j<=i;j++)
	{
		if(!vis1[i][j])
		{
			double res=dis(posx[i],posx[j],posy[i],posy[j]);
			addEdge(i,j,dirt*res);
			addEdge(j,i,dirt*res);
		}
	}

之后就可以以 $0$ 号点为起点跑 Dijkstra 了，我使用的是有加了堆优化后的 Dijkstra，记得初始化距离数组。

template<class T>
class cmp
{
	public:bool operator()(T A,T B){return A.dis>B.dis;}
};
priority_queue<node,vector<node>,cmp<node>> q; //创建小根堆
void dijkstra(int s)
{
	q.push({0,s});
	distanc[s]=0;
	while(!q.empty())
	{
		int u=q.top().p; q.pop();
		if(!vis[u])
		{
			vis[u]=1;
			for(int i=head[u];i;i=edge[i].nxt)
			{
				int v=edge[i].to;
				if(distanc[v]>distanc[u]+edge[i].w)
				{
					distanc[v]=distanc[u]+edge[i].w;
					q.push(node{distanc[v],v});
				}
			}
		}
	}
}

最后 $distanc_{n+1}$ 即为最终答案。

完整代码

#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=1000;
const int M=499510;
const double inf=1145141919;
int n,m;
bool vis[N];
double distanc[N];
int head[N];
int cnt=0;
struct Edge
{
	int to,nxt;
	double w;
}edge[M<<1];
void addEdge(int u,int v,double w)  //加边
{
	++cnt;
	edge[cnt]={v,head[u],w};
	head[u]=cnt;
}
struct node
{
	double dis;
	int p;
};
template<class T>
class cmp
{
	public:bool operator()(T A,T B){return A.dis>B.dis;}
};
priority_queue<node,vector<node>,cmp<node>> q; //创建小根堆
void dijkstra(int s)
{
	q.push({0,s});
	distanc[s]=0;
	while(!q.empty())
	{
		int u=q.top().p; q.pop();
		if(!vis[u])
		{
			vis[u]=1;
			for(int i=head[u];i;i=edge[i].nxt)
			{
				int v=edge[i].to;
				if(distanc[v]>distanc[u]+edge[i].w)
				{
					distanc[v]=distanc[u]+edge[i].w;
					q.push(node{distanc[v],v});
				}
			}
		}
	}
}

double dis(double xa,double xb,double ya,double yb)
{
	return sqrt((xa-xb)*(xa-xb)+(ya-yb)*(ya-yb));
}
bool vis1[N][N];
double dirt,rome;
double posx[N],posy[N];
signed main()
{
	cin>>dirt>>rome;
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>posx[i]>>posy[i];
	while(1)
	{
		int x,y;
		cin>>x>>y;
		if(x==0&&y==0) break;
		vis1[x][y]=vis1[y][x]=true;
		double res=dis(posx[x],posx[y],posy[x],posy[y]);
		addEdge(x,y,rome*res);
		addEdge(y,x,rome*res);
	}
	cin>>posx[0]>>posy[0]>>posx[n+1]>>posy[n+1];
	for(int i=0;i<=n+1;i++)
		for(int j=0;j<=i;j++)
		{
			if(!vis1[i][j])
			{
				double res=dis(posx[i],posx[j],posy[i],posy[j]);
//				cout<<i<<","<<j<<":"<<res<<endl;
				addEdge(i,j,dirt*res);
				addEdge(j,i,dirt*res);
			}
		}
//	memset(distanc,0x3f,sizeof distanc);
	for(int i=0;i<=n+10;i++) distanc[i]=inf;
	dijkstra(0);
//	for(int i=0;i<=n+1;i++) cout<<distanc[i]<<" ";
	cout<<fixed<<setprecision(4)<<distanc[n+1];
	return 0;
}