「USACO 2007 Nov. Gold」Cow Relays奶牛接力赛 - 动态规划+矩阵快速幂 | Bill Yang's Blog
0%

「USACO 2007 Nov. Gold」Cow Relays奶牛接力赛 - 动态规划+矩阵快速幂

题目大意

求出从S->E经过K条边的最短路。


初步想法

我们可以想到一个显然的思路(动规):
设$f[i,j]$表示经过i条边到达j点的最短路径长度。

时间复杂度:$O(n^2k)\quad n\le100\quad k<=10^6$
明显超时。


优化方案

能否对动规进行优化呢?
观察原式的转移只与上一个状态i-1与k有关,而i-1是定值,故只与k有关
再观察数据范围,n比较小而k比较大
再观察方程,是不是和这个方程长得很像?

这正是经过k条边最短路计数的方程。
没错,我们可以类似的使用矩阵快速幂进行优化。


定义矩阵乘法:

这个似乎与floyd长得有点像?但是并不是floyd,状态意义不一样。
然后我们就可以进行愉快的矩阵快速幂啦。
注意对原图的点进行离散化,点的范围就变成了边的范围。


代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<map>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
typedef long long LL;
const int maxn=105;
struct Matrix {
LL n,m,a[maxn][maxn];
Matrix(LL n,LL m) {
this->n=n;
this->m=m;
memset(a,0,sizeof(a));
}
Matrix(LL n,LL m,char E) { //单位矩阵
this->n=n;
this->m=m;
memset(a,0,sizeof(a));
for(int i=1; i<=n; i++)a[i][i]=1;
}
void init(LL n,LL m) {
this->n=n;
this->m=m;
memset(a,0,sizeof(a));
}
LL* operator [] (const LL x) {
return a[x];
}
Matrix operator = (Matrix b) {
init(b.n,b.m);
for(int i=1; i<=b.n; i++)
for(int j=1; j<=b.m; j++)
a[i][j]=b[i][j];
}
Matrix operator + (Matrix& b) {
for(int i=1; i<=b.n; i++)
for(int j=1; j<=b.m; j++)
a[i][j]+=b[i][j];
}
void operator += (Matrix& b) {
*this=*this+b;
}
Matrix operator - (Matrix& b) {
for(int i=1; i<=b.n; i++)
for(int j=1; j<=b.m; j++)
a[i][j]-=b[i][j];
}
void operator -= (Matrix& b) {
*this=*this-b;
}
Matrix operator * (LL k) {
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
a[i][j]*=k;
}
void operator *= (LL k) {
*this=*this*k;
}
Matrix operator * (Matrix& b) {
Matrix c(n,b.m);
for(int i=1; i<=n; i++)
for(int j=1; j<=b.m; j++) {
c[i][j]=0;
LL tmp=1e17;
for(int k=1; k<=m; k++)
if(a[i][k]!=0&&b[k][j]!=0)tmp=min(tmp,a[i][k]+b[k][j]);
if(tmp!=1e17)c[i][j]=tmp;
}
return c;
}
void operator *= (Matrix& b) {
*this=*this*b;
}
Matrix operator ^ (LL b) {
Matrix ans=*this,a=*this;
b--;
while(b>0) {
if(b&1)ans=ans*a;
a*=a;
b>>=1;
}
return ans;
}
void Output() {
for(int i=1; i<=n; i++) {
for(int j=1; j<=m; j++)
printf("%lld ",a[i][j]);
putchar('\n');
}
}
};
int n,m,Start,End,step=0;
map<int,int>vst;
int main() {
n=Get_Int();
m=Get_Int();
Start=Get_Int();
End=Get_Int();
if(!vst.count(Start))vst[Start]=++step;
if(!vst.count(End))vst[End]=++step;
Matrix G(m,m);
for(int i=1; i<=m; i++) {
int v=Get_Int(),x=Get_Int(),y=Get_Int();
if(!vst.count(x))vst[x]=++step;
if(!vst.count(y))vst[y]=++step;
G[vst[x]][vst[y]]=G[vst[y]][vst[x]]=v;
}
G=G^n;
printf("%lld\n",G[vst[Start]][vst[End]]);
return 0;
}
姥爷们赏瓶冰阔落吧~