POJ 3613 Cow Relays （FLoyd + 矩阵快速幂）

Cow Relays

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 4471		Accepted: 1778

Description

For their physical fitness program, N (2 ≤ N ≤ 1,000,000) cows have decided to run a relay race using the T (2 ≤ T ≤ 100) cow trails throughout the pasture.

Each trail connects two different intersections (1 ≤ I_1i ≤ 1,000; 1 ≤ I_2i ≤ 1,000), each of which is the termination for at least two trails. The cows know the length_i of each trail (1 ≤ length_i  ≤ 1,000), the two intersections the trail connects, and they know that no two intersections are directly connected by two different trails. The trails form a structure known mathematically as a graph.

To run the relay, the N cows position themselves at various intersections (some intersections might have more than one cow). They must position themselves properly so that they can hand off the baton cow-by-cow and end up at the proper finishing place.

Write a program to help position the cows. Find the shortest path that connects the starting intersection (S) and the ending intersection (E) and traverses exactly N cow trails.

Input

* Line 1: Four space-separated integers: N, T, S, and E
* Lines 2..T+1: Line i+1 describes trail i with three space-separated integers: length_i , I_1i , and I_2i

Output

* Line 1: A single integer that is the shortest distance from intersection S to intersection E that traverses exactly N cow trails.

Sample Input

2 6 6 4
11 4 6
4 4 8
8 4 9
6 6 8
2 6 9
3 8 9

Sample Output

10

Source

USACO 2007 November Gold

 

本题的大意就是问从S 到 T 经过边得个数恰为k的最短路是多少。

 

参考国家队集训论文 08年的  矩阵乘法在信息学中的应用

01邻接矩阵A的K次方C=A^K,C[i][j]表示i点到j点正好经过K条边的路径数

 对应于这道题,对邻接图进行K次floyd之后,C[i][j]就是点i到j正好经过K条边的最短路

但是K次floyd难免复杂度太高了。 所以可以使用快速幂的方法，二分的往上求解

 

题意：

求从一个点s 到 一点 e 经过 n 条边的最短路经是多少（可以有重边）：

看到很难多解题报告说的是n 个点 ，其实，n 条边 应该是 n - 1 个点 

题解：

 

我们知道线性代数中有：在只 含有 01邻接矩阵 A的K次 方C=A^K，C[i][j]表示i点到j点正好经过K条边的路径数。

 

而floyd则是每次使用一个中间点k去更新i,j之间的距离，那么更新成功表示i,j之间恰有一个点k时的最短路，如果做N - 1次floyd那么不就是i,j之间借助N - 1 个点时的最短路了

当 c[i][j] > a[i][k] + a[k][j]  则更新

第二次将c[i][j]拷贝回到a[i][j]当中，并将c[i][j]重新置为INF，再做一次，则是在原来的基础上在i,j之间再用一个点k来松弛，这时候i,j之间实际上已经是两个点了，

但是这个题的   n （边数太大）我们要用到 倍增法，其实即使 二分思想  例如  经过 5  条边 把  （4 个点）  ==  两个 2 条边的  松驰一次 ；

 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>

using namespace std;

int N,T,S,E,num;
map<int,int> mp;

struct Matrix{
    int ma[210][210];
    void clear(){
        memset(ma,0x3f,sizeof(ma));     //初始化一定要大，否则WA
    }
};

Matrix Floyd(Matrix a,Matrix b){
    Matrix dis;
    dis.clear();
    for(int k=1;k<=num;k++)     //一次floyd  是找到一个中间点
        for(int i=1;i<=num;i++)
            for(int j=1;j<=num;j++)
                if(dis.ma[i][j]>a.ma[i][k]+b.ma[k][j])
                    dis.ma[i][j]=a.ma[i][k]+b.ma[k][j];
    return dis;
}

Matrix Pow(Matrix a,int k){
    Matrix ans=a;
    while(k){
        if(k&1){
            ans=Floyd(ans,a);
        }
        a=Floyd(a,a);
        k>>=1;
    }
    return ans;
}

int main(){

    //freopen("input.txt","r",stdin);

    Matrix a;
    while(~scanf("%d%d%d%d",&N,&T,&S,&E)){
        num=0;
        mp.clear();
        a.clear();
        int u,v,w;
        while(T--){
            scanf("%d%d%d",&w,&u,&v);
            if(mp[u]==0)
                mp[u]=++num;
            if(mp[v]==0)
                mp[v]=++num;
            if(a.ma[mp[u]][mp[v]]>w)
                a.ma[mp[u]][mp[v]]=a.ma[mp[v]][mp[u]]=w;
        }
        Matrix ans=Pow(a,N-1);      // N 条边  ，经过 N-1 个点 
        printf("%d\n",ans.ma[mp[S]][mp[E]]);
    }
    return 0;
}