01 #include <bits/stdc++.h>
02 using namespace std;
03
04 #define N 105
05 #define INF 1e9
06
07 int dis1[N][N], dis2[N][N];
08 int mp[N][N], n, m;
09
10 void fun1(int dis[N][N]) {
11 static bool vis[N];
12 for (int i = 1; i <= n; i++) {
13 for (int j = 1; j <= n; j++) {
14 dis[i][j] = mp[i][j];
15 }
16 }
17 for (int i = 1; i <= n; i++) {
18 for (int j = 1; j <= n; j++) vis[j] = 0;
19 for (int k = 1; k <= n; k++) {
20 int now = 0;
21 for (int j = 1; j <= n; j++) {
22 if (!vis[j] && (!now || dis[i][now] > dis[i][j]))
23 now = j;
24 }
25 vis[now] = 1;
26 for (int j = 1; j <= n; j++) {
27 if(!vis[j]&&dis[i][j] > dis[i][now]+mp[now][j]){
28 dis[i][j] = dis[i][now] + mp[now][j];
29 }
30 }
31 }
32 }
33 }
34 void fun2(int dis[N][N]) {
35 for (int i = 1; i <= n; i++) {
36 for (int j = 1; j <= n; j++) {
37 dis[i][j] = mp[i][j];
38 }
39 }
40 for (int i = 1; i <= n; i++) {
41 for (int j = 1; j <= n; j++) {
42 for (int k = 1; k <= n; k++) {
43 dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
44 }
45 }
46 }
47 }
48
49 int main() {
50 cin >> n >> m;
51 for (int i = 1; i <= n; i++) {
52 for (int j = 1; j <= n; j++) {
53 if (i == j) mp[i][j] = 0;
54 else mp[i][j] = INF;
55 }
56 }
57 for (int i = 1; i <= m; i++) {
58 int u, v, w;
59 cin >> u >> v >> w;
60 mp[u][v] = w;
61 }
62 fun1(dis1);
63 fun2(dis2);
64 int ans = 0;
65 for (int i = 1; i <= n; i++) {
66 for (int j = 1; j <= n; j++) {
67 if (dis1[i][j] != dis2[i][j])
68 ans++;
69 }
70 }
71 cout << ans << endl;
72 return 0;
73 }

为什么说第一个dijkstra打错了？