POJ --- 3613 (K步最短路+矩阵快速幂+floyd)

Cow Relays

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

Sample Output

10

题意：在无向图中有n条边，现在给出你一个起点S和一个终点E，让你求从S到E经过且仅K条边的最短路径。注意此题中K远大于n，如果K小于n的话直接一边广搜就过了，第一次没注意到这个条件敲了一个BFS，结果WA了。

思路：此题正解应该是矩阵乘法，但是重定义了，区别于线性代数里面的乘法（其实可以看出无论哪种定义，只要能推出矩阵在该定义下满足交换律即可，因为可以用快速幂来加速）。
设原图G对应的邻接矩阵为M，则M的k次幂中M[i][j]就表示从i点到j点经过k条边路径的个数！那么只需要重新定义一下矩阵乘法：M[i][j]表示从i点到j点的的最短路径长度，即M[i][j] = min(M[i][j],M[i][k]+M[k][j])(这个就是floyd算法的核心，DP思想)，可以证明该定义满足交换律，因此可以用快速幂，考虑M^2,它表示从i到j经过2条边的最短路径，同理推出M^n表示从i到j经过n条边的最短路径，因此本题得解。
关于矩阵乘法的应用是参考2008年国家集训队论文《矩阵乘法在信息学中的应用》（俞华程）中看到的，网上此题解法大都参考该论文，在网上看了别人解释的没怎么看懂，直接看论文去了，发现论文里面讲的很明白也很透彻，但是经过别人转述意思可能就不一样了，其实我也说的不怎么清楚，所以建议直接去看论文。
网盘下载地址：http://yunpan.cn/QNeFIw2wIef4B （访问密码：7b0c）

 1 #include<cstdio>
 2 #include<string>
 3 #include<cstring>
 4 #include<iostream>
 5 #include<algorithm>
 6 #define MAXN 111
 7 using namespace std;
 8 class Matrix{
 9     public:
10         int m[MAXN][MAXN];
11         Matrix(){
12             memset(m, -1, sizeof(m));
13         }
14 };
15 int N = 0;
16 Matrix mtMul(Matrix A, Matrix B){
17     Matrix tmp;
18     for(int i = 0;i < N;i ++)
19         for(int j = 0;j < N;j ++)
20             for(int k = 0;k < N;k ++){
21                 if(A.m[i][k] == -1 || B.m[k][j] == -1) continue;
22                 int temp = A.m[i][k] + B.m[k][j];
23                 if(tmp.m[i][j] == -1 || tmp.m[i][j] > temp) tmp.m[i][j] = temp;
24             }
25     return tmp;
26 }
27 Matrix mtPow(Matrix A, int k){
28     if(k == 1) return A;
29     Matrix tmp = mtPow(A,  k >> 1);
30     Matrix res = mtMul(tmp, tmp);
31     if(k & 1) res = mtMul(res, A);
32     return res;
33 }
34 int main(){
35     int cnt[1111];
36     int n, t, s, e;
37     int u, v, w;
38     /* freopen("in.c", "r", stdin); */
39     while(~scanf("%d%d%d%d", &n, &t, &s, &e)){
40         N = 0;
41         Matrix G;
42         memset(cnt, -1, sizeof(cnt));
43         for(int i = 0;i < t;i ++){
44             scanf("%d%d%d", &w, &u, &v);
45             if(cnt[u] == -1) cnt[u] = N++;
46             if(cnt[v] == -1) cnt[v] = N++;
47             G.m[cnt[u]][cnt[v]] = w;
48             G.m[cnt[v]][cnt[u]] = w;
49         }
50         Matrix tmp = mtPow(G, n);
51         printf("%d
",tmp.m[cnt[s]][cnt[e]]);
52     }
53     return 0;
54 }

另外附上BFS的错误代码：

 1 #include<queue>
 2 #include<cstdio>
 3 #include<string>
 4 #include<cstring>
 5 #include<algorithm>
 6 #define MAXN 1111
 7 using namespace std; 
 8 class Status{
 9     public:
10         int pre, w, cnt; 
11         bool operator < (const Status &a) const{
12             return w < a.w; 
13         }
14 }; 
15 typedef struct{
16     int to, next, w; 
17 }Edge; 
18 Edge edge[211]; 
19 priority_queue<Status>q; 
20 int head[MAXN], N, T, S, E; 
21 void addedge(int u, int v, int w, int k){
22     edge[k].to = v; 
23     edge[k].next = head[u]; 
24     edge[k].w = w; 
25     head[u] = k++; 
26     edge[k].to = u; 
27     edge[k].next = head[v]; 
28     edge[k].w = w; 
29     head[v] = k; 
30 }
31 void bfs(int s){
32     while(!q.empty()) q.pop(); 
33     Status tmp; 
34     tmp.pre = s; 
35     tmp.w = tmp.cnt = 0; 
36     q.push(tmp); 
37     while(!q.empty()){
38         Status p = q.top(); 
39         int v = p.pre; 
40         q.pop(); 
41         for(int i = head[v]; ~i; i = edge[i].next){
42             int u = edge[i].to; 
43             if(u == E && p.cnt+1 == N){
44                 printf("%d
", p.w+edge[i].w); 
45                 return; 
46             }else if(u != E){
47                 Status t; 
48                 t.pre = u; 
49                 t.w = p.w+edge[i].w; 
50                 t.cnt = p.cnt+1;
51                 q.push(t); 
52             }
53         }
54     }
55 }
56 int main(){
57     int length, u, v, k; 
58     /* freopen("in.c", "r", stdin); */ 
59     while(~scanf("%d%d%d%d", &N, &T, &S, &E)){
60         memset(head, -1, sizeof(head)); 
61         k = 0; 
62         for(int i = 0; i < T; i ++){
63             scanf("%d%d%d", &length, &u, &v); 
64             addedge(u, v, length, k); 
65             k += 2; 
66         }
67         bfs(S); 
68     }
69     return 0; 
70 }