[Acwing] 345. 牛站 Floyd + 快速幂倍增

前言

快速幂思想还是不怎么会活用啊,我怎么就写题解了呢

又打算什么时候补呢?为什么不是今天就解决了呢?

又要拖到什么时候呢? 传送门 :

思路

这题一开始有一点像 B e l l m a n Bellman Bellman 但是 B e l l m a n Bellman Bellman是不超过k

条边的最短路(虽然看到题解有人用这个求出来,但是我不会 😦

因此这题和 B e l l m a n Bellman Bellman不一样

我们令 F l o y d Floyd Floyd 状态表示 : f [ k , i , j ] f[k,i,j] f[k,i,j]从点 i i i到点 j j j经过恰好 k k k条边的最短路 状态计算 : f [ a + b , i , j ] = m i n ( f [ a , i , j ] + f [ b , i , j ] ) f[a+b,i,j] = min(f[a,i,j]+f[b,i,j]) f[a+b,i,j]=min(f[a,i,j]+f[b,i,j])

但是显然,我们不能通过枚举每一个分界点 k k k来做出这题

但是我们可以通过被整的做法:例如K =38 ( 100110 ) 2 (100110)_2 (100110)2​,我们只需要从 2 , 4 , 32 这 三 个 答 案 转 移 过 来 就 行 了 2,4,32这三个答案转移过来就行了 2,4,32这三个答案转移过来就行了 因此处理如下

CODE

int k,m,S,E;

int g[N][N] ; 
int res[N][N];

map ids;
int n;
void mul(int a[][N],int b[][N],int c[][N])
{
	int temp[N][N];
	memset(temp,0x3f,sizeof temp);
	
	for(int k=1;kk>>m>>S>>E;
	//答案边数 , 图边数, 起点,终点
	
	//离散化
	if(ids.count(S) == 0) ids[S] = ++n;
	if(ids.count(E) == 0) ids[E] = ++n;
	
	memset(g,0x3f,sizeof g);
	S = ids[S];E = ids[E];
	
	while(m -- )
	{
		int a,b,c;cin>>c>>a>>b;
		if(ids.count(a) ==  0) ids[a] = ++n;
		if(ids.count(b) ==  0) ids[b] = ++n;
		a = ids[a],b = ids[b];
		g[a][b] =  g[b][a] = min(g[a][b],c); 
	}
	
	//通过快速幂求经过 K条边
	qmi();
	cout