题解
c
n
t
[
i
]
[
j
]
cnt[i][j]
cnt[i][j] 表示
i
i
i 到
j
j
j 的最短边数量
外层枚举
k
k
k,
d
[
i
]
[
j
]
d[i][j]
d[i][j] 表示除了
i
i
i 和
j
j
j 其余点下标小于等于
k
k
k 时
i
i
i 和
j
j
j 的最短距离,再更新
对于为什么要把更新
c
o
u
n
t
count
count 的循环放在枚举
k
k
k 的循环里面,作以下解释:
首先复习以下
f
l
o
y
d
floyd
floyd 算法,起初是三维的,但是可以写作二维
f
l
o
y
d
{
状态表示
{
f
[
k
]
[
i
]
[
j
]
:
表示只经过前
k
个点
(
不考虑
i
,
j
两个端点
)
从
i
到
j
的距离
属性
:
m
i
n
状态计算:
f
[
k
]
[
i
]
[
j
]
=
{
f
[
k
−
1
]
[
i
]
[
j
]
:
不经过
k
从
i
到
j
f
[
k
−
1
]
[
i
]
[
k
]
+
f
[
k
−
1
]
[
k
]
[
j
]
:
经过
k
从
i
到
j
floyd\begin{cases}状态表示\begin{cases}f[k][i][j]:表示只经过前k个点(不考虑i,j两个端点)从i到j的距离\\属性:min\end{cases}\\状态计算:f[k][i][j]=\begin{cases}f[k-1][i][j]:不经过k从i到j\\f[k-1][i][k]+f[k-1][k][j]:经过k从i到j\end{cases}\end{cases}
floyd⎩⎨⎧状态表示{f[k][i][j]:表示只经过前k个点(不考虑i,j两个端点)从i到j的距离属性:min状态计算:f[k][i][j]={f[k−1][i][j]:不经过k从i到jf[k−1][i][k]+f[k−1][k][j]:经过k从i到j
每次更新的
c
n
t
cnt
cnt 是路径
k
→
i
→
k
k→i→k
k→i→k 的长度,首先看
w
[
k
]
[
i
]
w[k][i]
w[k][i] 是否存在,然后枚举
i
<
k
i<k
i<k,是为了防止重复计算路径
i
→
k
→
i
i→k→i
i→k→i 的长度(与路径
k
→
i
→
k
k→i→k
k→i→k 相同)。上述只考虑了路径长度为
2
2
2,但是当路径长度多起来,例如
k
→
i
→
j
→
k
k→i→j→k
k→i→j→k,有
i
<
k
<
j
i<k<j
i<k<j 时,会发现仍然会重复计算,所以不能只保证
k
k
k 确定时枚举
i
<
k
i<k
i<k,还要保证经过的点都要小于
k
k
k,不重不漏原则。
e
.
g
.
e.g.
e.g. 如下图,枚举
k
=
4
k=4
k=4 的时候,有路径
4
→
1
→
2
→
4
4→1→2→4
4→1→2→4,
4
→
3
→
4
4→3→4
4→3→4,
4
→
1
→
5
→
4
4→1→5→4
4→1→5→4;但是枚举
k
=
5
k=5
k=5 时也发现会美剧到路径
5
→
4
→
1
→
5
5→4→1→5
5→4→1→5,可能会出现重复计算
#include<iostream>usingnamespace std;typedeflonglong ll;constint mod =998244353, N =502;const ll inf =1e12;int n, m, w[N][N], cnt[N][N];
ll d[N][N];voidsolve(){
cin >> n >> m;for(int i =1; i <= n; i ++)for(int j =1; j <= n; j ++)
w[i][j]=0, d[i][j]= inf;for(int i =1; i <= n; i ++) d[i][i]=0;while(m --){int a, b, c; cin >> a >> b >> c;
w[a][b]= d[a][b]= c;
cnt[a][b]=1;}
ll minn = inf, count =0;for(int k =1; k <= n; k ++){for(int i =1; i <= n; i ++){for(int j =1; j <= n; j ++){if(d[i][j]> d[i][k]+ d[k][j]){
d[i][j]= d[i][k]+ d[k][j];
cnt[i][j]=1ll* cnt[i][k]* cnt[k][j]% mod;}elseif(d[i][j]== d[i][k]+ d[k][j]){
cnt[i][j]=(cnt[i][j]+1ll* cnt[i][k]* cnt[k][j])% mod;}}}for(int i =1; i < k; i ++){if(w[k][i]){if(w[k][i]+ d[i][k]< minn){
minn = w[k][i]+ d[i][k];
count = cnt[i][k];}elseif(w[k][i]+ d[i][k]== minn){
count =(count + cnt[i][k])% mod;}}}}if(minn == inf) minn = count =-1;
cout << minn <<' '<< count << endl;}intmain(){
cin.tie(nullptr)->sync_with_stdio(false);int T; cin >> T;while(T --)solve();return0;}