【牛站 / USACO2007】

题目

思路

离散化（降低空间复杂度）

$点的编号\in [1,1000]，但是点的个数最多为2\cdot T\in [4,200]$
$因此采用离散化处理可以降低空间复杂度$
采用映射unordered_map + 计数器n

类Floyd算法（算法核心）

首先回顾一下Floyd算法

for(int k = 1; k <= n; k++)
{
	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= n; j++)
		{
			g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
		}
	}
}

该算法的思路是考虑各个中转点来不断更新最短路径


可能会有疑问是关于中转点的遍历时机
但是只要记住一句话，路径可以按照任意结合的顺序形成：以 i 为中转点的大路径可能不会在 k = i 就被更新好，但是他所需要的，中转点为 i 的部分一定会在 k = i 之后被更新好

类Floyd

for(int k = 1; k <= n; k++)
    {
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                temp[i][j] = min(temp[i][j], a[i][k] + b[k][j]);
            }
        }
    }

该算法的思路是考虑各个中转点来更新最短路径


两者的区别在于，类Floyd不会拿用前一个中转点更新的路径继续更新以其他点为中转点的路径，换句话说：类Floyd只能用两个旧的状态迭代新的状态，不能使用新的状态进行迭代
这有一个好处：如果 $g$ 的初始状态集合是 $k$ 条边路径的集合，那么进行一次迭代（类Floyd）之后，新状态集合为 $k+k$ 条边路径的集合，由此，我们就可以控制一条路径含边的数量了

快速幂（降低时间复杂度）

k条边的路径可以按照任意结合的顺序形成
$例如：(a\Rightarrow b)\Rightarrow (b\Rightarrow c)\Rightarrow (c\Rightarrow d)（1+1+1），也可以（a\Rightarrow b）\Rightarrow (b\Rightarrow c\Rightarrow d)（1+2），更可以(a\Rightarrow b\Rightarrow c)\Rightarrow (c\Rightarrow d)（2+1）$


因此我们将k作二进制唯一分解。将g对应的边长值不断翻番，并且每次将g的边合并到ans中......
最终我们就可以得到对应边长值为k的邻接矩阵ans

关于一些细节

if(!id.count(S)) id[S] = ++n;
    S = id[S]; //为什么不写到if里？
    if(!id.count(E)) id[E] = ++n;
    E = id[E];

哪怕之前进行过离散化处理，此时点的编号也要更新才对啊。不能够说离散化处理了这个 id 就好了，我不用离散化之后的S，我还用原来的S

for (int i = 1; i <= n; i ++ ) ans[i][i] = 0; //为啥g[i][i]不能是0，这个非得是0

ans[i][i]必须为0是因为要mul(ans, ans, g)，即将ans 和 g 中的路径作合并，只有ans[i][i] = 0, ans[i][j] = ans[i][i] + g[i][j]才能够生效，将g[i][j]保存在ans中，否则 g 中 的一些路径没有按照预期进入ans中


同理，g 中不搞 g[i][i] = 0 是因为 g 的初态表示边为1的路径，i 到 i 算边为 0。如果搞g[i][i] = 0，mul(g, g, g) 迭代一次后，会存在边为（0+1）的路径，我们就丧失了对于边这个参数的掌控

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 210;

int g[N][N], ans[N][N];
unordered_map<int, int> id;
int k, m, S, E, n;

void mul(int c[][N], int a[][N], int b[][N])
{
    int temp[N][N];
    memset(temp, 0x3f, sizeof temp);
    for(int k = 1; k <= n; k++)
    {
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                temp[i][j] = min(temp[i][j], a[i][k] + b[k][j]);
            }
        }
    }
    memcpy(c, temp, sizeof temp);
}
void qmi()
{
    memset(ans, 0x3f, sizeof ans);
    for (int i = 1; i <= n; i ++ ) ans[i][i] = 0;
    while(k)
    {
        if(k & 1) mul(ans, ans, g);
        mul(g, g, g);
        k >>= 1;
    }
}
int main()
{
    cin >> k >> m >> S >> E;
    
    if(!id.count(S)) id[S] = ++n;
    S = id[S];
    if(!id.count(E)) id[E] = ++n;
    E = id[E];
    
    memset(g, 0x3f, sizeof g);
    for(int i = 1; i <= m; i++)
    {
        int a, b, c;
        cin >> c >> a >> b;
        if(!id.count(a)) id[a] = ++n;
        a = id[a];
        if(!id.count(b)) id[b] = ++n;
        b = id[b];
        g[a][b] = g[b][a] = min(g[a][b], c);
    }
    
    qmi();
    
    cout << ans[S][E];
    return 0;
}