P2886

题意

从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

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

设计 $dp[i][j]$ 表示从 $s$ 经过 $i$ 条边，到达 $j$ 点的最短路。然后对于每个 $i$，使用所有边更新一下即可。然后把 $i$ 滚动掉就行了。

这样就可以不用矩乘了，时间复杂度 $\Theta(nm)$。

#include<bits/stdc++.h>
#define int long long
#define R(x) x=read()
using namespace std;
inline int read() {
	int x=0,y=1;
	char e=getchar();
	while(e<'0'||e>'9') {
		if(e=='-')y=-1;
		e=getchar();
	}
	while(e>='0'&&e<='9') {
		x=(x<<1)+(x<<3)+(e^'0');
		e=getchar();
	}
	return x*y;
}
int n,m,s,e;
struct node {
	int u,v,w;
} a[105];
int dp[2][1005];
signed main() {
	R(n),R(m),R(s),R(e);
	for(int i=1; i<=m; ++i) {
		R(a[i].w),R(a[i].u),R(a[i].v);
	}
	memset(dp,0x3f,sizeof dp);
	dp[1][s]=0;
	int nw=1;
	for(int j=1; j<=n; ++j) {
		nw^=1;
		memset(dp[nw],0x3f,sizeof dp[nw]);
		for(int i=1,u,v,w; i<=m; ++i) {
			u=a[i].u,v=a[i].v,w=a[i].w;
			dp[nw][v]=min(dp[nw][v],dp[nw^1][u]+w);
			dp[nw][u]=min(dp[nw][u],dp[nw^1][v]+w);
		}
	}
	if(dp[nw][e]<=1e10)
		cout<<dp[nw][e];
	else cout<<"-1\n";
	return 0;
}