代码

#include <bits/stdc++.h>
using namespace std;
struct mat{int a[305][305];}g;
int n = 300,t,s,e,u,v,w,_n,num[500005],tot;
mat m(mat a,mat b){
	mat c;
	for(int i = 1;i <= tot;i ++){
		for(int j = 1;j <= tot;j ++){
			c.a[i][j] = 1e9;
			for(int k = 1;k <= tot;k ++) c.a[i][j] = min(c.a[i][j],a.a[i][k] + b.a[k][j]);
		}
	}
	return c;
}
mat p(mat a,int b){
	mat ans = a;b --;
	while(b) ans = (b & 1 ? m(ans,a) : ans),a = m(a,a),b >>= 1;
	return ans;
}
int main(){
	cin >> _n >> t >> s >> e;
	for(int i = 1;i <= n;i ++) for(int j = 1;j <= n;j ++) g.a[i][j] = 1e9;
	for(int i = 1;i <= t;i ++){
		cin >> u >> v >> w;
		if(!num[u]) num[u] = ++tot;
		if(!num[v]) num[v] = ++tot;
		g.a[num[u]][num[v]] = g.a[num[v]][num[u]] = w;
	}
//	for(int i = 1;i <= n;i ++) g.a[i][i] = 0;
	mat gg = p(g,_n);
	cout << gg.a[num[s]][num[e]];
	return 0;
}

一直输出 1e9……