题目大意：给定一个 N 个顶点，M 条边的无向图，求从起点到终点恰好经过 K 个点的最短路。

题解：设 \(d[1][i][j]\) 表示恰好经过一条边 i,j 两点的最短路，那么有 \(d[r+m][i][j]=min\{d[r][i][k]+d[m][k][j] \}\)，等价于矩阵乘法。

这道题 K 很大，可以用快速幂加速矩阵乘法。

代码如下

#include <cstdio>

#include <algorithm>

#include <memory.h>

using namespace std;

const int maxn=101;

int n,t,st,ed,tot,v[1010];

struct matrix{

	int dat[maxn][maxn];

	matrix(){memset(dat,0x3f,sizeof(dat));}

	inline int* operator[](int i){return dat[i];}

	friend matrix operator*(matrix& x,matrix& y){

		matrix z;

		for(int i=1;i<=tot;i++)

			for(int j=1;j<=tot;j++)

				for(int k=1;k<=tot;k++)

					z[i][j]=min(z[i][j],x[i][k]+y[k][j]);

		return z;

	}

}d,ans;

void read_and_parse(){

	scanf("%d%d%d%d",&n,&t,&st,&ed);

	for(int i=1,from,to,w;i<=t;i++){

		scanf("%d%d%d",&w,&from,&to);

		if(!v[from])v[from]=++tot;

		if(!v[to])v[to]=++tot;

		from=v[from],to=v[to];

		d[from][to]=d[to][from]=min(d[from][to],w);

	}

	st=v[st],ed=v[ed];

}

void solve(){

	ans=d,--n;

	for(;n;d=d*d,n>>=1)if(n&1)ans=ans*d;

	printf("%d\n",ans[st][ed]);

}

int main(){

	read_and_parse();

	solve();

	return 0;

}