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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
| for(int k=1;k<=p;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
w[i][j]=min(w[i][j],w[i][k]+w[k][j]);
```
当 p=n 时，该代码就是我们所熟知的 floyd，然而小 A 为了让代码跑的更快点，所以想减少 p 的值。
令 Di,j 为最小的非负整数 x，满足当 p=x 时，点 i 与点 j 之间的最短路被正确计算了。
现在你需要求 ∑ni=1∑nj=1Di,j，虽然答案不会很大，但为了显得本题像个计数题，你还是需要将答案对 998244353 取模后输出。
**Input**
第一行一个正整数 T(T≤30) 表示数据组数
对于每组数据：
第一行两个正整数 n,m(1≤n≤1000,m≤2000)，表示点数和边数。
保证最多只有 5 组数据满足 max(n,m)>200
接下来 m 行，每行三个正整数 u,v,w 描述一条边权为 w 的边 (u,v)，其中 1≤w≤109
**Output**
输出 T 行，第 i 行一个非负整数表示第 i 组数据的答案
### 思路
就是求最大松弛点中的最小值， 当时比赛的时候不管怎么样都不能顿悟， 还是太菜了呀。
### AC代码
```cpp
#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <vector>
#include <utility>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#define eps 1e-8
typedef long long ll;
const int N = 1e5 + 5;
typedef std::pair<ll, int> P;
const int INF = 0x3f3f3f3f;
const ll llINF = 0x3f3f3f3f3f3f3f3f;
const ll mod = 998244353;
struct edge{
int v;
ll w;
int ne;
}ed[N];
int head[1003];
bool vis[1003];
ll dis[1003];
int d[1003][1003];
int cnt, m, n;
void init(){
cnt = 0;
memset(head, -1, sizeof head);
memset(d, 0, sizeof d);
}
void addedge(int u, int v, ll w){
ed[cnt].v = v, ed[cnt].w = w;
ed[cnt].ne = head[u];
head[u] = cnt++;
}
std::priority_queue<P, std::vector<P> , std::greater<P> >q;
void dijk(int s){
memset(vis, false, sizeof vis);
for (int i = 1; i <= n; i++)
dis[i] = 1e18;
dis[s] = 0;
q.push(P(0, s));
while(!q.empty()){
int u = q.top().second;
q.pop();
if (vis[u])
continue;
vis[u] = true;
for (int i = head[u]; ~i; i = ed[i].ne){
int v = ed[i].v;
if (dis[v] > dis[u] + ed[i].w){
dis[v] = dis[u] + ed[i].w;
q.push(P(dis[v], v));
if (dis[v] == ed[i].w) {
d[s][v] = 0;
}
else {
d[s][v] = std::max(d[s][u], u);
}
}
else if (dis[v] == dis[u] + ed[i].w){
d[s][v] = std::min(d[s][v], std::max(u, d[s][u]));
}
}
}
}
int main(){
std::ios::sync_with_stdio(false);
ll ans;
int t, u, v;
ll w;
std::cin >> t;
while(t--){
std::cin >> n >> m;
init();
for (int i = 0; i < m; i++){
std::cin >> u >> v >> w;
addedge(u, v, w);
addedge(v, u, w);
}
for (int i = 1; i <= n; i++)
dijk(i);
ans = 0;
for (int i = 1; i <= n; i++){
for (int j = 1; j <= n; j++){
ans = (ans + d[i][j]) % mod;
}
}
std::cout << ans % mod << "\n";
}
return 0;
}
|