poj3613 Cow Relays(最短路/矩阵快速幂+floyd/经过k条边的APSP)

题目

t(t<=100)条边，每个边两端的点的编号在1-1e3之间

边权w<=1e3

给一个起点S，一个终点E，

求S->E经过n<=1e6条边的最短路

思路来源

https://blog.****.net/monster__yi/article/details/51069236

马老师！！！

题解

我今天要吹爆mls！！！

本来wa得不能自已，马老师一点就AC了

不能加自己到自己的0的边，

即不能令A[i][i]=0

如以下样例：

Input:
3 1 1 2
3 1 2
Output:
9

矩阵A[i][j]代表i->j的经过1条边的最短路，

而则为代表i->j的经过k条边的最短路，

矩阵乘法的过程，行*列的时候，

相当于加一个点，即枚举加一条边构成新的最短路

Trick

快速幂里面，要把B先赋成A这个矩阵，然后倍增少一次即可

因为对于A这种矩阵，

既不能把零次单位矩阵B全赋成INF，也不能全赋0，

也不能主对角线赋0，其余地方赋INF

所以就赋A之后，少搞一次就可以了，

B的倍增和A的倍增是一样的

代码

#include <iostream>
#include <algorithm> 
#include <cstring>
#include <cstdio>
#include <vector>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
typedef vector<int> vec;
typedef vector<vec> mat;
struct edge
{
	int u,v,w;
}e[205];
int id[1005],cnt,a[2005];
mat mul(mat &A, mat &B){
    mat C(A.size(), vec(B[0].size()));
    for(int i=0;i<C.size();++i)
	{
		for(int j=0;j<C[0].size();++j)
		{
		  C[i][j]=INF;
	    }   
	}
    for(int i = 0; i < A.size(); i++)
	{
        for(int j = 0; j < B[0].size(); j++)
		{
			for(int k = 0; k < B.size(); k++)
		    {
			   C[i][j]=min(C[i][j],A[i][k]+B[k][j]);
            }
        }
    }
    return C;
}
 
mat modpow(mat A, ll n){
    mat B(A.size(), vec(A.size()));
    B=A;n--;
    while(n)
	{
        if(n & 1) B = mul(B, A);
        A = mul(A, A);
        n >>= 1; 
    }
    return B;
}
int n,t,S,E;
int main()
{
	while(~scanf("%d%d%d%d",&n,&t,&S,&E))
	{
		cnt=0;
		memset(id,0,sizeof(id));
		for(int i=0;i<t;++i)
		{
			scanf("%d%d%d",&e[i].w,&e[i].u,&e[i].v);
		    a[cnt++]=e[i].u;
			a[cnt++]=e[i].v; 
		} 
		sort(a,a+cnt);
		int num=unique(a,a+cnt)-a;
		for(int i=0;i<num;++i)id[a[i]]=i;
		mat A(num, vec(num));
		for(int i=0;i<num;++i)
		{
			for(int j=0;j<num;++j)
			{
			  A[i][j]=INF;
		    }
		}
		for(int i=0;i<t;++i)
		{
			A[id[e[i].u]][id[e[i].v]]=min(A[id[e[i].u]][id[e[i].v]],e[i].w);
			A[id[e[i].v]][id[e[i].u]]=min(A[id[e[i].v]][id[e[i].u]],e[i].w);
			//printf("A[%d][%d]:%d\n",id[e[i].u],id[e[i].v],e[i].w);
		}
		/*for(int i=0;i<num;++i)
		{
			for(int j=0;j<num;++j)
			printf("A[%d][%d]:%d\n",i,j,A[i][j]);
		}*/
        A = modpow(A, n);
        printf("%d\n",A[id[S]][id[E]]); 
    }
    return 0; 
}