萌新求助矩乘
查看原帖
萌新求助矩乘
716260
SegmentTree_楼主2024/5/3 21:14

输出都没有

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e3+5;
const int maxn = 500;
int tot;
int aa[1000005];
struct matrix{
	int a[maxn][maxn];
	matrix(){
		memset(a, 0, sizeof a);
	}
	void memse(){
		memset(a, 0x3f3f3f3f, sizeof a);
	}
	void build(){
		for (int i = 1;i <= tot;i++){
			a[i][i] = 1;
		}
	}
	friend matrix operator *(const matrix a, const matrix b){
		matrix c;
		c.memse();
		for (int k = 1;k <= tot;k++){
			for (int i = 1;i <= tot;i++){
				for (int j = 1;j <= tot;j++){
					c.a[i][j] = min(c.a[i][j], (a.a[i][k] + b.a[k][j]));
				}
			}
		}
		return c;
	}
}ans, a;
void qpow(matrix a1, int b){
	ans = a1;
	b--;
	while (b){
		if (b & 1) ans = ans * a1;
		a1 = a1 * a1;
		b >>= 1;
	}
}
int main(){
	//ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	int n, t, s, e;
	cin >> n >> t >> s >> e;
	a.memse();
	for (int i = 1;i <= t;i++){
		int w, u, v;
		cin >> w >> u >> v;
		if (!aa[u]) aa[u] = ++tot;
		if (!aa[v]) aa[v] = ++tot;
		a.a[aa[u]][aa[v]] = a.a[aa[v]][aa[u]] = w;
	}
	/*
	for (int i = 1;i <= tot;i++){
		for (int j = 1;j <= tot;j++) cout << a.a[i][j] << ' ';
		cout << '\n';
	}*/
	qpow(a, n);
	cout << ans.a[aa[s]][aa[e]];
	return 0;
}
2024/5/3 21:14
加载中...