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

2013-07-11

POJ3613Cow Relays （FLoyd + 矩阵快速幂）Cow RelaysTime Limit:?1000MS?Memory Limit:?65536KTotal Submis

POJ 3613 Cow Relays （FLoyd + 矩阵快速幂）
Cow RelaysTime Limit:?1000MS?Memory Limit:?65536KTotal 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 ≤?I1i?≤ 1,000; 1 ≤?I2i?≤ 1,000), each of which is the termination for at least two trails. The cows know the?lengthi?of each trail (1 ≤?lengthi? ≤ 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:?lengthi?,?I1i?, and?I2i

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

Sample Output
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;}
?

热点排行

其他相关

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