题解 P6833 【[Cnoi2020]雷雨】

· · 题解

洛谷 P6833 题解

现在才知道不能加防抄袭，这是修改的，求管理重新放上。

十年 OI 一场空，不开 long long 见祖宗。

题目描述

给定一个起点，和两个终点，求最小的起点到两个终点的路径的并集上的点权和。

其实就是说如果两条路径重复了一段的话，那一段只算一次。

题目分析

其实会发现这个闪电的路径是由三条最短路组成的，一条连向雷雨云，两条分别连向红魔馆和迷途竹林。

考虑枚举三条路径的交叉点，并用 dijkstra（spfa死了）求出这个点到雷雨云，红魔馆和迷途竹林的最短路。如果枚举每个点再求的话浪费多少时间复杂度就不用说了，所以可以从三个源点各跑一遍 dijkstra，最后计算答案时把从三个源点跑出来的最短路相加即可。

跑 dijkstra 时可以把起始点的最短路设成点权，然后到任意一个点后就加上新的点权。注意这样算的话枚举的交叉点的点权会被多算两次，计算答案时要减掉。

时间复杂度就是三遍 dijkstra，即 O(nm\times log(nm))，可过。

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
struct node
{
    long long x,y,dis;
    bool operator <(const node &b)const
    {
        return dis>b.dis;
    }
};
long long num[1001][1001],dis[3][1001][1001];
int n,m,a,b,c,dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};
void dijkstra(int k,int sx,int sy)
{
    priority_queue<node> q;
    q.push((node){sx,sy,num[sx][sy]});
    bool vis[1001][1001]={0};
    for(int i=1;i<=1000;i++)
    {
        for(int j=1;j<=1000;j++)
        {
            dis[k][i][j]=1e18;
        }
    }
    dis[k][sx][sy]=num[sx][sy];
    while(!q.empty())
    {
        int x=q.top().x,y=q.top().y;
        q.pop();
        if(vis[x][y])
        {
            continue;
        }
        vis[x][y]=1;
        for(int i=0;i<4;i++)
        {
            int tx=x+dx[i],ty=y+dy[i];
            if(tx<1||tx>n||ty<1||ty>m)
            {
                continue;
            }
            if(dis[k][tx][ty]>dis[k][x][y]+num[tx][ty])
            {
                dis[k][tx][ty]=dis[k][x][y]+num[tx][ty];
                q.push((node){tx,ty,dis[k][tx][ty]});
            }
        }
    }
}
int main()
{
    scanf("%d%d%d%d%d",&n,&m,&a,&b,&c);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            scanf("%lld",&num[i][j]);
        }
    }
    dijkstra(0,1,a);
    dijkstra(1,n,b);
    dijkstra(2,n,c);
    long long ans=1e18;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            ans=min(ans,dis[0][i][j]+dis[1][i][j]+dis[2][i][j]-2*num[i][j]);//注意这里交叉点的部分会多算两次，所以要减掉
        }
    }
    printf("%lld",ans);
    return 0;
}

谢谢观看！