文章目录
题目分析错因代码
题目
[NOI Online #2 入门组] 魔法
分析
d
p
[
i
]
[
j
]
[
k
]
dp[i][j][k]
dp[i][j][k] 表示
i
i
i 到
j
j
j 用
k
k
k 次魔法的最小代价，
f
[
i
]
[
j
]
f[i][j]
f[i][j] 表示
i
i
i 到
j
j
j 用一次魔法的最小代价：
d
p
[
i
]
[
j
]
[
k
]
=
min
{
d
p
[
i
]
[
u
]
[
k
−
1
]
+
f
[
u
]
[
j
]
,
f
[
i
]
[
u
]
+
d
p
[
u
]
[
j
]
[
k
−
1
]
}
dp[i][j][k] = \min \{dp[i][u][k - 1] + f[u][j], f[i][u] + dp[u][j][k - 1]\}
dp[i][j][k]=min{dp[i][u][k−1]+f[u][j],f[i][u]+dp[u][j][k−1]} 枚举的中转节点
u
u
u 恰似 Floyd 算法，于是套路矩阵加速即可，
g
[
i
]
[
j
]
g[i][j]
g[i][j] 表示不用魔法
i
i
i 到
j
j
j 最小代价，则答案为
g
×
f
k
g \times f^k
g×fk 其中
×
\times
× 号不是常规矩阵乘法，而与 DP 式相似，由于
min
\min
min 有对
+
+
+ 的分配率（
a
+
min
{
b
,
c
}
=
min
{
a
+
b
,
a
+
c
}
a + \min\{b, c\} = \min\{a + b, a + c\}
a+min{b,c}=min{a+b,a+c}），所以这个矩阵运算有结合律，所以可以快速幂。
错因
DP 式列错，想的是转移的最后一条边用魔法，死活快速幂做不出来，实际上是最后一段的某一条边用魔法；分层图骗分还没有连
u
→
u
′
u \to u'
u→u′ 代价为
0
0
0 的边，70 pts
→
\to
→ 50 pts。
代码
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <set>
#include <vector>
typedef long long LL
;
const int MAXN
= 100;
const int MAXM
= 2500;
const int MAXK
= 1000;
const LL INF
= 1ll << 60;
int N
, M
, K
;
int U
[MAXM
+ 5], V
[MAXM
+ 5], W
[MAXM
+ 5];
LL G
[MAXN
+ 5][MAXN
+ 5], One
[MAXN
+ 5][MAXN
+ 5], C
[MAXN
+ 5][MAXN
+ 5];
LL
Mul(LL A
[MAXN
+ 5][MAXN
+ 5], LL B
[MAXN
+ 5][MAXN
+ 5]) {
for (int i
= 1; i
<= N
; i
++)
for (int j
= 1; j
<= N
; j
++) {
C
[i
][j
] = INF
;
for (int k
= 1; k
<= N
; k
++)
C
[i
][j
] = std
::min(C
[i
][j
], A
[i
][k
] + B
[k
][j
]);
}
for (int i
= 1; i
<= N
; i
++)
for (int j
= 1; j
<= N
; j
++)
A
[i
][j
] = C
[i
][j
];
}
int main() {
scanf("%d%d%d", &N
, &M
, &K
);
for (int i
= 1; i
<= N
; i
++)
for (int j
= 1; j
<= N
; j
++)
if (i
!= j
)
G
[i
][j
] = One
[i
][j
] = INF
;
for (int i
= 1; i
<= M
; i
++) {
int u
, v
, w
; scanf("%d%d%d", &u
, &v
, &w
);
G
[u
][v
] = w
, U
[i
] = u
, V
[i
] = v
, W
[i
] = w
;
}
for (int k
= 1; k
<= N
; k
++)
for (int i
= 1; i
<= N
; i
++)
for (int j
= 1; j
<= N
; j
++)
G
[i
][j
] = std
::min(G
[i
][j
], G
[i
][k
] + G
[k
][j
]);
if (!K
)
return printf("%lld", G
[1][N
]), 0;
for (int k
= 1; k
<= M
; k
++)
for (int i
= 1; i
<= N
; i
++)
for (int j
= 1; j
<= N
; j
++)
One
[i
][j
] = std
::min(One
[i
][j
], G
[i
][U
[k
]] + G
[V
[k
]][j
] - W
[k
]);
while (K
) {
if (K
& 1)
Mul(G
, One
);
Mul(One
, One
);
K
>>= 1;
}
printf("%lld", G
[1][N
]);
return 0;
}
