poj 3613 Cows relays 恰好K步最短路 floyd 快速幂+离散化

缘起

日常浪费生命~ poj 3613 Cows relays

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
给定一张M条边的无向带权图，求从起点S到终点E恰好经过K条边的最短路径。 
2 <= M <= 100; 2 <= K <= 1000000。保证每个连边的点度至少为2。

【输入】
第一行给出四个整数，K， M，S，E ， 其中S和E表示起点和终点
第二行到第M+1行每行三个整数 length，A，B 表示A和B之间连接的边的权是 length

【输出】
从S到E恰好K步的最短路

【样例输入】
2 6 6 4
11 4 6
4 4 8
8 4 9
6 6 8
2 6 9
3 8 9

【样例输出】
10

【限制】
1s

此题是08年IOI国家集训队的论文. 《矩阵乘法在信息学中的应用 · 浙江省杭州二中 俞华程》

本文顺便来介绍一下这篇论文.

首先是矩阵乘法的复杂度结论的介绍

直接按照定义进行矩阵乘法时间复杂度是O (abc)，其中a; b; c分别表示两个矩阵大小是a b以及b c。将两个N * N的矩阵相乘，朴素算法的时间复杂度为O (N^3)。其他有一些算法有更低的复杂度，例如 Strassen 算法时间复杂度约为O (N^2.81)。而现有的算法中理论复杂度最低的是 Coppersmith—Winograd 算法，时间复杂度约为O (N^2.36)。