BZOJ2143 【飞飞侠】题解

对于这种一个点连出去的每条边权值都相等的图的最短路,我们可以考虑使用并查集优化。

我们考虑更换优先队列中的点权为dis+w,而不是dis,这样就相当于按照一个点能将其可以到达的点能更新到的值从小到大,可以保证每个点只被更新一次,因为点能被更新到的值会越来越大,所以其必然被可以到达它的第一个点更新,这样就可以把复杂度降到n^2logn

推荐博客:https://www.cnblogs.com/HolyK/p/9858182.html

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
int nmsumidminxvis[4], ans[4];
int a[155][155], b[155][155];
int dis[155][155], fa[155][155];
struct node
{
    int x;
    int y;
    int dis;
    node(int xx = 0int yy = 0int dd = 0)
    {
        x = xx;
        y = yy;
        dis = dd;
    }
    bool operator<(const node &bbconst
    {
        return dis > bb.dis;
    }
};
priority_queue<nodeq;
int getfather(int xint y)
{
    if (!fa[x][y])
        return y;
    fa[x][y] = getfather(xfa[x][y]);
    return fa[x][y];
}
void dijkstra(int Xint Y)
{
    memset(fa0sizeof(fa));
    memset(dis, -1sizeof(dis));
    fa[X][Y] = Y + 1;
    dis[X][Y] = 0;
    q.push(node(XYdis[X][Y] + a[X][Y]));
    while (!q.empty())
    {
        int x = q.top().x;
        int y = q.top().y;
        q.pop();
        for (int i = max(1x - b[x][y]); i <= min(nx + b[x][y]); ++i)
            for (int j = max(1y - (b[x][y] - abs(i - x))); j <= min(my + (b[x][y] - abs(i - x))); ++j)
            {
                j = getfather(ij);
                if (j > m || j > y + (b[x][y] - abs(i - x)))
                    break;
                dis[i][j] = dis[x][y] + a[x][y];
                q.push(node(ijdis[i][j] + a[i][j]));
                fa[i][j] = j + 1;
            }
    }
    return;
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1i <= n; ++i)
        for (int j = 1j <= m; ++j)
            scanf("%d", &b[i][j]);
    for (int i = 1i <= n; ++i)
        for (int j = 1j <= m; ++j)
            scanf("%d", &a[i][j]);
    int x1y1x2y2x3y3;
    scanf("%d%d%d%d%d%d", &x1, &y1, &x2, &y2, &x3, &y3);
    dijkstra(x1y1);
    if (dis[x2][y2] == -1)
        vis[2] = 1;
    if (dis[x3][y3] == -1)
        vis[3] = 1;
    ans[2] += dis[x2][y2];
    ans[3] += dis[x3][y3];
    dijkstra(x2y2);
    if (dis[x3][y3] == -1)
        vis[3] = 1;
    if (dis[x1][y1] == -1)
        vis[1] = 1;
    ans[3] += dis[x3][y3];
    ans[1] += dis[x1][y1];
    dijkstra(x3y3);
    if (dis[x1][y1] == -1)
        vis[1] = 1;
    if (dis[x2][y2] == -1)
        vis[2] = 1;
    ans[1] += dis[x1][y1];
    ans[2] += dis[x2][y2];
    for (int i = 1i <= 3; ++i)
        if (!vis[i] && (!id || ans[i] < minx))
        {
            id = i;
            minx = ans[i];
        }
    if (!id)
        printf("NO");
    else
    {
        if (id == 1)
            printf("X");
        else if (id == 2)
            printf("Y");
        else if (id == 3)
            printf("Z");
        putchar('\n');
        printf("%d"minx);
    }
    return 0;

} 

评论

此博客中的热门博文