题意

从A出发 恰经过T条边 到达B的最短路程 可以重复经过点或边

做法

这个是一个比较典的板子 就是 定长最短路

wiki

具体思路可以看wiki

这里解释一下 为什么可以用矩乘

$L_{k+1}[i,j]=min(L_k[i,p]+L_k[p,j]) 1 <= p <= n$

min是满足结合律的 min(a,b,c)=min(a,min(b,c))

因此我们把累加变为了min，乘变成了加，这样就可以用矩乘了

code

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

const long long N = 1010;

long long vis[N];

long long T, n, m, s, t;

struct mat {
	long long mp[N][N];
} g;

void read() {
	cin >> T >> m >> s >> t;
	long long cnt = 0;
	if(!vis[s]) vis[s] = ++cnt;
	if(!vis[t]) vis[t] = ++cnt;
	for(long long i = 1; i <= m; i++) {
		long long u, v, w;
		cin >> w >> u >> v;
		if(!vis[u]) vis[u] = ++cnt;
		if(!vis[v]) vis[v] = ++cnt;
		g.mp[vis[u]][vis[v]] = g.mp[vis[v]][vis[u]] = w;
	}
	n = cnt;
	for(long long i = 1; i <= n; i++) {
		for(long long j = 1; j <= n; j++) {
			if(g.mp[i][j] == 0) g.mp[i][j] = INT_MAX;
		}
	}
}

mat fun(mat a,mat b) {
	mat c;
	for(long long i = 1; i <= n; i++) {
		for(long long j = 1; j <= n; j++) {
			c.mp[i][j] = INT_MAX;
		}
	}
	for(long long i = 1; i <= n; i++) {
		for(long long j = 1; j <= n; j++) {
			for(long long k = 1; k <= n; k++) {
				c.mp[i][j] = min(c.mp[i][j],a.mp[i][k]+b.mp[k][j]);
			}
		}
	}
	return c;
}

void init() {

}

void compute() {
	mat ans = g;
	T--;
	while(T) {
		if(T & 1) ans = fun(ans,g);
		g = fun(g,g);
		T >>= 1;
	}
	if(ans.mp[vis[s]][vis[t]] == INT_MAX) cout << -1;
	else cout << ans.mp[vis[s]][vis[t]]; 
}

void clear() {

}

void run() {
	read();
	init();
	compute();
	clear();
}

void fre(string s) {
	freopen((s+".in").c_str(),"r",stdin);
	freopen((s+".ww").c_str(),"w",stdout);
}

int main() {
//	fre("ex");
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	run();
	return 0;
}

警钟长鸣

注意看清楚读入数据的顺序 是先读入的边权 再读入的 端点

挂了92pts