题目链接https://www.luogu.com.cn/problem/P2886

分析

这道题，的确是个一眼题。。。。
除了离散化不想说什么。
最开始的时候发现这题的输入很坑，它给的点的编号不是连续的，也就是说虽然最多只有100个点但点的编号可能会很大，那就只能离散化了，最开始用的去重+二分，调了半天不对，发现这很麻烦，于是换了一种，点的编号没什么用，除了当一个标记之外，不需要维护相对大小，所以直接用一个数字代替就好，后来发现最开始的离散化求去重后数组长度写错了。。。
至于这道题怎么做，我真的懒得说了。请参考一个月前写的东西：
NOI ONLINE魔法
如果没什么思路，这里还有个ppt。（感觉如果很久前我分享的时候听的认真的同志应该都能做出来。。）
PPT

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1e2+10;
int t,dis[N][N],f[N][N];
struct Edge{
    int to,fro,val;
}e[N<<1];
int tt,que[N*N*N];
void Mul(int a[N][N],int b[N][N],int c[N][N]){
    int tep[N][N];
    memset(tep,0x3f,sizeof(tep));
    for(int i=1;i<=tt;i++)
    for(int j=1;j<=tt;j++)
    for(int k=1;k<=tt;k++)
        tep[i][j]=min(tep[i][j],b[i][k]+c[k][j]);
    memcpy(a,tep,sizeof(tep));
}
int main(){
    memset(f,0x3f,sizeof(f));
    int n,S,E;
    scanf("%d%d%d%d",&n,&t,&S,&E);
    for(int i=1;i<=t;i++){
        int a,b,c;
        scanf("%d%d%d",&c,&a,&b);
        if(!que[a])que[a]=++tt;
        if(!que[b])que[b]=++tt;
        f[que[a]][que[b]]=f[que[b]][que[a]]=min(f[que[a]][que[b]],c);
    }
    memcpy(dis,f,sizeof(f));
    n--;
    while(n){
        if(n&1){
            Mul(dis,f,dis);
        }
        Mul(f,f,f);
        n>>=1;
    }
    printf("%d\n",dis[que[S]][que[E]]);
}

POJ3613 Cow Relays 矩阵快速幂

原文：https://www.cnblogs.com/anyixing-fly/p/12783470.html