P2914 [USACO08OCT]Power Failure G题解

· · 题解

是一道很有意思的最短路题目哦！

题意

因为邪恶的暴风雨，可怜的 FJ 需要你帮忙修复电路。用电路使 编号 1 \sim 9 的电站连通，恢复电路。

（如图，图为题中高配版。配合样例食用更佳）

每个电站的坐标都在图中标出，并且标上了序号。红色的电线是完好无损的。需要你在两个电站中新连接的线不能超过一个限制 M，求在原来电线的基础上计算出需要修复电路的距离。

为什么使用最短路

若网络中的每条边都有一个数值（长度、成本、时间等），则找出两个结点之间总权和最小的路径就是最短路问题。

根据题意，需要我们选择最短的路程（电线的长度）将编号 1\sim n 的点连通，所以使用最短路算法解决。

思路

把这一切抽象成图，跑最短路。已经有部分的边，因为这些是完好无损的边，所以在图中这些边没有耗费，边的权值为 0。剩下的边初始化为点与点在坐标中的距离。

Floyd 算法会超时。跑 Dijkstra，时间复杂度 O((n+m)\log n)。当边权值超过限制 M 时，不更新答案。

当最终答案仍然为初始化的一个很大的数时，无解。

图中给出的蓝色的电线就是我们需要连上的。其它的会在代码里注释。也可以用用优先队列优化 Dijkstra 算法。

ACcode

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>

using namespace std;

const int maxn=2e3+55;
const int oo=2e9+55;
int N,W;
double M;
struct zb{
    double x,y;
}z[maxn];
double g[maxn][maxn],dis[maxn];
bool vis[maxn];

//计算点与点在坐标中的距离 
double coordinate(zb x,zb y){
    return sqrt((x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y));
}

signed main(void){

    cin>>N>>W;
    cin>>M;

    for(int i=1;i<=N;i++){
        cin>>z[i].x>>z[i].y;
    }   

    //建图初始化 
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            g[i][j]=coordinate(z[i],z[j]);
        }
    }

    for(int i=1;i<=W;i++){
        int x,y;
        cin>>x>>y;
        g[x][y]=g[y][x]=0;
    }

    //答案数组初始化 
    for(int i=1;i<=maxn;i++){
        dis[i]=oo;
    }

    //Dijkstra 
    dis[1]=0;
    for(int i=1;i<=N;i++){
        int tmp=oo,id;
        for(int j=1;j<=N;j++){
            if(vis[j]==0 && dis[j]<tmp){
                tmp=dis[j];
                id=j;
            }
        }
        vis[id]=1;
        for(int j=1;j<=N;j++){
            if(dis[j]>dis[id]+g[id][j] && g[id][j]<M && j!=id){
                dis[j]=dis[id]+g[id][j];
            }
        }
    }

    if(dis[N]==oo){
        printf("-1\n");
    } else {
        cout<<(int)(dis[N]*1000)<<endl;
    }

    return 0;
}