P1907 设计道路 题解

· · 题解

题目传送门

也许更好的阅读体验？

前置芝士

建图方式

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

d=\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}

先建立 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;
}