luogu 2886 牛继电器

胡扯

可能大佬们都会这题，但是如果有大佬不知道（tan90°）这种很有趣又感觉很实用的知识点的话说不定能帮点忙。

理解

• 看到这个边的数量，一下子→Floyd。
• 那么对于Floyd，每次加入一个点扩展是不是就多了一条边呢？所以会想到扩展k次点来得到最短路。但是k很大，那么考虑一下，对于一个图的邻接矩阵G而言(初始连通1，不连通0)一开始的读入后得到的G就是表示两点是否直接可达。
• 每一次选择中间扩展点k的时候，[i,k]+[k,j]是不是很眼熟？floyed的过程实际上是类似于矩阵乘法的,只不过要求松弛而已。使用矩乘，就可以模拟扩展点的时候计算此时经过了n条边的最短路径长度。
• 一次floyed后所求的矩阵就是在i,j中插入一个点的k。那么不断插入，就能一直推下去推到经过k条边的最短路。要注意每次都使用新的数组，用以前的数组进行更新，才能保证，每次只用到了一个点来更新。
• 然后加上离散化！加上快速幂！快乐AC（其实咸鱼想了半天才想明白

对于这题思想拓展推荐大家可以去看一下国家队论文《矩阵乘法在信息学中的应用》，十分实用。
对于矩阵和递推的关系可以去看一些相关博客
对于基本的矩乘操作推荐博客http://blog.csdn.net/wust_zzwh/article/details/52058209，更深层次的就搜一搜自己get吧(:з」∠)

下面题解，没啥好注释的，拼音取名解决一切疑问（。）

#include <cstdio>
#include <cstring>
#define re register int
#define fp(i,a,b) for(re i=a,I=b;i<=I;++i)
#define min(a,b) a<b?a:b
typedef struct juzhen
{
    long long v[210][210];
}M;
M Gra,ans;
int K,T,S,E;
long long n;
long long p[2010];
M floyd(M a,M b)
{
    M c;
    memset(c.v,0x3f,sizeof(c.v));
    int i,j,k;
    fp(k,1,n)fp(i,1,n)fp(j,1,n) c.v[i][j]=min(c.v[i][j],a.v[i][k]+b.v[k][j]);
    return c;
}
void chen(int x)
{
    while(x)
    {
        if(x&1) ans=floyd(ans,Gra);
        Gra=floyd(Gra,Gra);
        x>>=1;
    }
}
int main()
{
    scanf("%d%d%d%d",&K,&T,&S,&E);
    memset(Gra.v,0x3f,sizeof(Gra.v));
    memset(ans.v,0x3f,sizeof(ans.v));
    fp(i,1,T){
        re x,y,z;
        scanf("%d%d%d",&z,&x,&y);
        if(!p[x]) p[x]=++n;if(!p[y]) p[y]=++n;
        Gra.v[p[x]][p[y]]=Gra.v[p[y]][p[x]]=min(z,Gra.v[p[y]][p[x]]);
    }
    for(int i=1;i<=n;i++) ans.v[i][i]=0;
    chen(K);
    printf("%lld",ans.v[p[S]][p[E]]);
    return 0;
}