题目描述

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

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

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

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

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

2≤T≤100
,
2≤N≤106

样例

输入样例：

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

输出样例：

10

算法1

yoho ～

写在前面

（（（如果您们不太会矩阵快速幂的话请右转百度一下，蒟蒻我不知道还有没有写矩乘的博客或题解的时间了呢～～

这道题的话，借助了机房大佬们的人类智慧，蒟蒻我终于把这道题码了出来，这道题的思路很巧妙呢～（据说和DDP思路一样呢～，当然，蒟蒻我不会跟您们讲的，因为我也不会啊～～～～）

step 1：

首先如果没有边数限制那就是SPFA或DIJ裸题。

但是如果考虑到边数限制，因为可以一条边走多次，考虑到上面两种算法，事实上可能需要记录用多少步走到每一个点的最小代价，当然，这样的空间复杂度我们是不能接受的，然后考虑下面的问题

step 2：

思考一波，发现最短路算法里还有个floyed！！！

然后把它拿出来（emmm

发现这个算法的本质就是在枚举k的时候，我们已经求出了每两个点之间（可能）经过1～k-1内的点的最短路，
然后我们大力强迫他每一次转移都多经过一个点，也就是对于每一个点的dis值，每一次新的转移只可能是再多经过一个k点，也就是多增加一条边得到，这样我们就可以通过两个矩阵转移n次得到答案了呢～（？？？突然矩阵？？？，好吧，是下面这样的）

step 3

事实上，学过矩阵快速幂的同学们可能会发现floyed的转移方程即 dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);

是不是长得挺想矩乘的转移方程的～

没错，我们矩乘就是这么优秀，他还可以转移min或max值，只要将转移方程由d[i][j]=d[i][j]+d[i][k]*d[k][j];
变成d[i][j]=min/max(d[i][j],d[i][k]+d[k][j]);对于这道题的话当然是取min
于是我们就可以矩阵加速了

step 4
了解矩阵快速幂的同学们应该知道，矩阵快速幂最难的是构造转移矩阵，这东西在这道题里直接就上dis数组即可，（dis[i][i]=0;dis[i][j]=min(inf,val[i][j])）（就是你怎么初始化floyed里的dis就怎么初始化他就行了）

初始矩阵的话我们只用第一行即可（f[1][i]表示已经借助矩阵转移了x次，也就是经过x条边，到i的最短路径是多少）

于是就做完了。。。。。。

易错点

1.要注意矩乘不满足交换律（额，但是本题的这种矩乘的话它得满足结合律，只有这样我们才能保证正确性）

2.点太多了所以我们要大力李三花（离散化）点的编号（当然大佬们可以用map但是不比我毒瘤快多少呢～）

3.emmmmm？？？

时间复杂度

T就看作不同的点的数量吧

大概是T^2*log(n)

C++ 代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
    int x=0;int f=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
    return x*f;
}
const int maxn = 250;
const int inf  = 0x3f3f3f3f;
struct node{
    int d[maxn][maxn];
};
node st,f,ee;
int n,m,s,e,cnt;
void init(){
    for(int i=1;i<=cnt;i++){
        for(int j=1;j<=cnt;j++){
            if(i==1){
                if(j!=s)    st.d[i][j]=inf;
                else  st.d[i][j]=0;
            }
            else st.d[i][j]=0;
        }   
    }   
}
node mul(node a,node b){
    node res;
    for(int i=1;i<=cnt;i++){
        for(int j=1;j<=cnt;j++){
            res.d[i][j]=inf;
            for(int k=1;k<=cnt;k++){
                res.d[i][j]=min(res.d[i][j],a.d[i][k]+b.d[k][j]);
            }
        }
    }
    return res;
}
node pow(node a,int b){
    node res=a;b--;
    while(b){
        if(b&1) res=mul(res,a);
        a=mul(a,a);
        b>>=1;
    }
    return res;
}
struct xxx{
    int u,v,w;
}edge[40000];
int num[40000];
signed main(){
    n=read();m=read();s=read();e=read();
    memset(f.d,0x3f,sizeof(f.d));
    cnt=0;
    for(int i=1;i<=m;i++){
        int w=read();int u=read();int v=read();
        edge[i].u=u;edge[i].v=v;edge[i].w=w;
        num[++cnt]=u;num[++cnt]=v;  
    }
    sort(num+1,num+1+cnt);
    cnt=unique(num+1,num+1+cnt)-num-1;
    for(int i=1;i<=m;i++){
        int u=lower_bound(num+1,num+1+cnt,edge[i].u)-num;
        int v=lower_bound(num+1,num+1+cnt,edge[i].v)-num;
        f.d[u][v]=f.d[v][u]=min(f.d[u][v],edge[i].w);
    }
    s=lower_bound(num+1,num+1+cnt,s)-num;
    e=lower_bound(num+1,num+1+cnt,e)-num;
    init();
    node ans=mul(st,pow(f,n));
    printf("%lld",ans.d[1][e]);
    return 0;
}