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;
}