http://acm.pku.edu.cn/JudgeOnline/problem?id=3613
求经过N条边的最短路 (2 ≤ N ≤ 1,000,000）
倍增floyd，主体是矩阵乘法。考虑一个x边的路径矩阵和y边的路径矩阵，两个矩阵用类似floyd的方法结合起来，就得到x+y边的路径矩阵，现在想要得到N边路径矩阵
然后就是“快速幂”的思想啦...把N拆成2的幂，只需要log(N)次矩阵乘法就搞定
伪floyd O(N^3)，所以总的时间复杂度O(logN*n^3) 其中n是点的个数 由于最多100个边，所以n最大200
虽说只有最多200个点，然而点点序号却很迷的到了1000，所以用了离散化，把点的序号映射到1～200范围
答案矩阵开始时候应该为单位矩阵 在这个倍增floyd定义下 单位矩阵应该是迹为0 其他值为正无穷
#include<cstdio>
#include<cstring>
#include<map>
using namespace std;
const int maxn = , INF = 0x3f3f3f3f;
map<int, int>M;
int cnt, n, t, s, e;
struct floyd{
int a[maxn][maxn];
floyd(){
memset(a, INF, sizeof(a));
}
floyd operator * (const floyd& b){
floyd c;
for(int i = ; i <= cnt; i++)
for(int j = ; j <= cnt; j++)
for(int k = ; k <= cnt; k++)
if(c.a[i][j] > a[i][k] + b.a[k][j])
c.a[i][j] = a[i][k] + b.a[k][j];
return c;
}
}st, ans;
void quick(){
// ans = st;
// n--;
while(n){
if(n&){
ans = ans*st;
}
st = st * st;
n >>= ;
}
}
int main(){
scanf("%d%d%d%d", &n, &t, &s, &e);
cnt = ;
while(t--){
int w, x, y;
scanf("%d%d%d", &w, &x, &y);
if(M[x])
x = M[x];
else
x = M[x] = ++cnt;
if(M[y])
y = M[y];
else
y = M[y] = ++cnt;
st.a[x][y] = st.a[y][x] = w;
}
for(int i = ; i <= cnt; i++)
ans.a[i][i] = ;
quick();
printf("%d", ans.a[M[s]][M[e]]);
return ;
}