AcWing 牛站

标签：总结   main   mem   pow   eof   str   esc   次方   win   

AcWing 牛站

Description

• 给定一张由T条边构成的无向图，点的编号为1~1000之间的整数。

  求从起点S到终点E恰好经过N条边（可以重复经过）的最短路。

Input

• 第1行：包含四个整数N，T，S，E。

  第2..T+1行：每行包含三个整数，描述一条边的边长以及构成边的两个点的编号。

Output

• 输出一个整数，表示最短路的长度。

Sample Input

2 6 6 4
11 4 6
4 4 8
8 4 9
6 6 8
2 6 9
3 8 9

Sample Output

10

Data Size

10

题解：

• 矩阵快速幂。
• 挺妙的一道题。当我们设A(i, j)为i到j经过0条边的最短路。那么显然原图的邻接矩阵就是A矩阵，我们再设B(i, j)为i到j经过1条边的最短路。 那么我们只需要枚举中间点k，然后在A矩阵中进行松弛即可。那么A矩阵枚举一次中转点得到B矩阵。那么我要求经过N条道的矩阵。那么不就是A矩阵枚举N次中转点吗？即A矩阵的N次方次运算。但是，矩阵乘法中发生了变动，即变成了类似Floyd的东西，因为要求最短路。你可能会问，为什么快速幂又不用变呢？快速幂只是保证进行运算的次数。
• 那么枚举中转点后，如果更新呢？举个例子，假设现在有4个点1、2、3、4。现要更新2到1的最短路。我们可以看看dis(2, 1) + dis(1, 1)是否

• 总结：进行N次运算，一次运算的定义是枚举中转点进行松弛操作，运算的实现用矩阵乘法的运算法则和Floyd的思想实现。

• 代码细节：原图时(i, i)不能置为0。因为我可以问你从1点到1点经过5条道路的最短路是多少（显然不是0

#include 
#include 
#include 
#define N 205
using namespace std;

struct A
{
    int m[N][N];
    A() {memset(m, 0x3f, sizeof(m));}
} a;
struct E {int u, v, w;} e[N];
int k, m, sta, en, n;
int b[N], f[1000005];

A mul(A x, A y)
{
    A z;
    for(int i = 1; i >= 1;
    }
    return r;
}

int main()
{
    cin >> k >> m >> sta >> en;
    for(int i = 1; i > e[i].w >> e[i].u >> e[i].v;
        if(!f[e[i].u]) f[e[i].u] = ++n;
        if(!f[e[i].v]) f[e[i].v] = ++n;
    }
    for(int i = 1; i 

AcWing 牛站

标签：总结   main   mem   pow   eof   str   esc   次方   win   

原文地址：https://www.cnblogs.com/BigYellowDog/p/11380623.html