河南第十届ACM省赛-I-Transmit information

ACM模版

描述

题解

十分有趣的一道题，可以用 dp 解，也可以用倍增法 Floyd 解，标程是后者。

这里是求经过 N 条边的最短路，简单的最短路算法已经无法满足需求，我们需要对图进行 N 次 Floyd，由于每次 Floyd 都不是直接对原花费矩阵操作，而是将值存在另一个矩阵中，所以可以保证每次 Floyd 都能够只收缩一条边，这样 N 次 Floyd 后就能保证通过了 N 条边获取的最短路。这里由于 Floyd 是 O(n3) 复杂度，所以进行 N 次 Floyd 显然是不现实的，这里我们可以利用矩阵快速幂的思路搞矩阵加速，这样就使其变为可行了。最后总复杂度为 O(n3logn)，客观讲，这个解法不难理解，但是没有接触过的真是不好想到，具体代码十分容易看明白，就不多说了。

代码

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <queue>

using namespace std;

const int MAXN = 1005;

int k, m, s, t;
int ans[MAXN][MAXN];
int tmp[MAXN][MAXN];
int tmp_[MAXN][MAXN];
int used[MAXN], v[MAXN], cnt;

void floyd(int c[][MAXN], int a[][MAXN], int b[][MAXN])
{
    for (int k = 0; k < cnt; k++)
    {
        for (int i = 0; i < cnt; i++)
        {
            for (int j = 0; j < cnt; j++)
            {
                if (c[v[i]][v[j]] > a[v[i]][v[k]] + b[v[k]][v[j]])
                {
                    c[v[i]][v[j]] = a[v[i]][v[k]] + b[v[k]][v[j]];
                }
            }
        }
    }
}

void copy(int a[][MAXN], int b[][MAXN])
{
    for (int i = 0; i < cnt; i++)
    {
        for (int j = 0; j < cnt; j++)
        {
            a[v[i]][v[j]] = b[v[i]][v[j]];
        }
    }
}

void slove(int k)
{
    while (k)
    {
        if (k & 1)
        {
            floyd(tmp_, ans, tmp);
            copy(ans, tmp_);
            memset(tmp_, 0x3f, sizeof(tmp_));
        }
        floyd(tmp_, tmp, tmp);
        copy(tmp, tmp_);
        memset(tmp_, 0x3f, sizeof(tmp_));
        k >>= 1;
    }
}

void init()
{
    cnt = 0;
    memset(tmp, 0x3f, sizeof(tmp));
    memset(tmp_, 0x3f, sizeof(tmp_));
    memset(ans, 0x3f, sizeof(ans));
    for (int i = 0; i < MAXN; i++)
    {
        ans[i][i] = 0;
    }
}

int main()
{
    init();

    scanf("%d%d%d%d", &k, &m, &s, &t);

    int x, y, w;
    for (int i = 0; i < m; i++)
    {
        scanf("%d%d%d", &w, &x, &y);
        if (!used[x])
        {
            used[x] = 1;
            v[cnt++] = x;
        }
        if (!used[y])
        {
            used[y] = 1;
            v[cnt++] = y;
        }
        if (tmp[x][y] > w)
        {
            tmp[x][y] = tmp[y][x] = w;
        }
    }

    slove(k);

    printf("%d\n", ans[s][t]);

    return 0;
}