4457 . 全點對最短路
Description
在西元7122年，建電社辦隨著時間逐漸成長，已經成為了一間成熟的社辦
作為一間成熟的社辦，整天走來走去還有想奇怪的演算法題目也是很正常的
今天他正在拯救卡在建中牆上的北一生時突然想到了一個問題
在台北市有 $N$ 個路口和 $M$ 條道路
由於現在是7122年，道路都是立體的，所以道路不會在路口以外的地方交叉
為了交通安全，所有道路都是單向道且可以表示為 $(A_i, B_i, w_i)$
表示這條路從 $A_i$ 通往 $B_i$，且需要花費 $w_i$ 分鐘的時間才能走完
現在社辦想要知道從每個路口出發，前往所有其他路口分別至少需要花費多少時間
為了方便輸出(X，我懶得生測資
所以請輸出所有點對間最短時間和模 $998244353$
也就是如果定義由路口 $C$ 走到路口 $D$ 的最短花費時間為 $dis(C,D)$
請輸出 $\sum\limits^n_{i=1}\sum\limits^n_{j=1} dis(i,j) \text{ mod } 998244353$
對了，如果無法從路口 $C$ 走到路口 $D$，那就把距離設成 $-1$ 吧
Input Format
$N$ $M$
$A_1$ $B_1$ $w_1$
$...$
$A_m$ $B_m$ $w_m$
Input Limits
$1 \leq n \leq 2000$
$0 \leq m \leq 5000$
$\forall i,1 \leq A_i,B_i \leq n, 1 \leq w_i \leq 10^{14}$
Output Format
輸出一個非負整數
Sample Input 1
4 4
1 2 1
2 3 2
3 4 3
4 1 4
1 2 1
2 3 2
3 4 3
4 1 4
Sample Output 1
60
Sample Input 2
2 0
Sample Output 2
998244351
Hints
Subtasks
| No. | Testdata Range | Score |
|---|
