本文主要是介绍POJ 3613 Cow Relays (Floyd + 矩阵快速幂 + 离散化 神题！)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 5611 | Accepted: 2209 |
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
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
题目链接：http://poj.org/problem?id=3613
题目大意：求从起点s到终点e经过k条边的最短路径
题目分析：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 个点时的最短路，i，j之间有n－1个点即有n条边，因为n比较大，考虑采用矩阵快速幂来求，还有就是这题的t比较小，但是l1，l2比较大，所以将其离散化，因为t最大为100，所以离散化后最多有200个点
#include <cstdio>
#include <cstring>
int h[205], cnt;struct matrix
{int m[205][205];matrix(){memset(m, 0x3f, sizeof(m));}
};matrix Floyd(matrix a, matrix b)
{matrix ans;for(int k = 1; k <= cnt; k++)for(int i = 1; i <= cnt; i++)for(int j = 1; j <= cnt; j++)if(ans.m[i][j] > a.m[i][k] + b.m[k][j])ans.m[i][j] = a.m[i][k] + b.m[k][j];return ans;
}matrix quickmod(matrix a, int k)
{matrix ans = a;while(k){if(k & 1)ans = Floyd(ans, a);k >>= 1;a = Floyd(a, a);}return ans;
}int main()
{int n, t, s, e;cnt = 1;matrix ans;scanf("%d %d %d %d", &n, &t, &s, &e);memset(h, 0, sizeof(h));for(int i = 0; i < t; i++){ int u, v, w;scanf("%d %d %d", &w, &u, &v);if(!h[u])h[u] = cnt++;if(!h[v])h[v] = cnt++;if(ans.m[h[u]][h[v]] > w)ans.m[h[u]][h[v]] = ans.m[h[v]][h[u]] = w;}ans = quickmod(ans, n - 1);printf("%d\n", ans.m[h[s]][h[e]]);
}这篇关于POJ 3613 Cow Relays (Floyd + 矩阵快速幂 + 离散化 神题！)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
