-
题目链接：
-
Update 6.16
最近看了下《算法导论》，惊奇地发现在在介绍\(APSP\) \((All Pairs Shortest Path)\)时的第一个方法就是此法，同时在思考题中看到了不少熟悉的问题，看来《算法导论》还是要多看一下
-
思路：
看到这题想了很久，想不到比较优的做法，然后看了书上的解法
感觉太妙了，将图论与矩阵加速递推结合了起来从而轻而易举地解决了这道题，实在是神奇。
首先我们构建邻接矩阵\(A\),最初\(A[i][j]\)表示从i到j直接相连路径长度(即不经过其他的点),若两点不直接相连或\(i==j\),都设为\(inf\)
很明显当\(n==0\)时最初的\(A[i][j]\)表示经过\(n\)条边的最短路
那么\(n!=0\)时呢？假设\(n==1\),那么我们只要将初始A矩阵进行如此运算:
\(A[i][j]=min_{1<=k<=n,k!=i,j}(A[i][k]+A[k][j])\)
此时\(A[i][j]\)当然就表示经过\(n\)条边时从\(i\)到\(j\)的最短路
那么当\(n==k\)时呢？好象我们需\(k\)次上述运算,但是仔细一看它很想我们的矩阵乘法,显然具有结合律 逃），然后矩阵快速幂就好了...
-
注意：
inf值最好设大一点，在这里卡了好久
节点数给出来是1000范围,矩阵乘法会超时，但是边数只有200范围，于是对节点编号离散化。
不知道为什么POJ上用C++会RE，要用G++
代码：
/*C++ 11*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cctype>
#include <vector>
#include <map>
#define ll long long
#define ri register int
using namespace std;
const int maxn=255;
const int inf=999999999;//inf值要设大
int tot=0;
struct Mat{
int g[maxn][maxn];
Mat operator ^(const int &k)const{
int c=k;
//Mat ans=Mat(n);
Mat ans=*this;
Mat res=ans;
while(c){
if(c&1)ans=ans*res;
res=res*res;
c=c>>1;
}
return ans;
}
Mat operator *(const Mat &b)const{
Mat ans;
for(ri i=1;i<=tot;i++){
for(ri j=1;j<=tot;j++){
ans.g[i][j]=inf;
}
}
for(ri i=1;i<=tot;i++){
for(ri j=1;j<=tot;j++){
int tmp=ans.g[i][j];
for(ri k=1;k<=tot;k++){
tmp=min(ans.g[i][j],g[i][k]+b.g[k][j]);
}
ans.g[i][j]=tmp;
}
}
return ans;
}
};
int N,t,s,e;
int di[198164],fx[maxn];
Mat a;
template <class T>inline void read(T &x){
x=0;int ne=0;char c;
while(!isdigit(c=getchar()))ne=c=='-';
x=c-48;
while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-48;
x=ne?-x:x;
return ;
}
int main(){
int dis,u,v;
read(N),read(t),read(s),read(e);
for(ri i=1;i<=maxn;i++){
for(ri j=1;j<=maxn;j++)
a.g[i][j]=inf;
}
for(ri i=1;i<=t;i++){
read(dis),read(u),read(v);
if(!di[u])di[u]=++tot,fx[tot]=u;
if(!di[v])di[v]=++tot,fx[tot]=v;
a.g[di[u]][di[v]]=dis;
a.g[di[v]][di[u]]=dis;
}
a=a^(N-1);
printf("%d\n",a.g[di[s]][di[e]]);
return 0;
}