公式
D - 都市ネットワーク / City Network 解説
by
D - 都市ネットワーク / City Network 解説
by
MMNMM
\(d(i,j)\) の値をすべての \((i,j)\) の組に対して計算することができれば、あとは \(O(N ^ 2)\) 時間の処理で答えを求めることができます。
ワーシャルフロイド法というアルゴリズムを用いると、\(N\) 頂点のグラフに対してすべての \(d(i,j)\) を \(O(N ^ 3)\) 時間で求めることができます。
これを使うことで、この問題を解くことができます。
実装例は以下のようになります。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int N, M;
cin >> N >> M;
vector<int> S(N);
for (int& s : S) {
cin >> s;
}
vector distance(N, vector(N, 400000000000));
for (int i = 0; i < M; ++i) {
int u, v, w;
cin >> u >> v >> w;
--u; // 0-indexed にする
--v;
distance[u][v] = distance[v][u] = w;
}
for (int i = 0; i < N; ++i) {
distance[i][i] = 0;
}
// ワーシャルフロイド法で d(i, j) を求める
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
for (int k = 0; k < N; ++k) {
distance[j][k] = min(distance[j][k], distance[j][i] + distance[i][k]);
}
}
}
// C[i] を求める
vector<int> C(N);
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
C[i] += distance[i][j] > S[i];
}
}
// 友好ペアの個数を求める
int ans = 0;
for (int i = 0; i < N; ++i) {
for (int j = i + 1; j < N; ++j) {
ans += distance[i][j] <= min(S[i], S[j]) && C[i] == C[j];
}
}
cout << ans << endl;
return 0;
}
N, M = map(int, input().split())
S = list(map(int, input().split()))
distance = [[400000000000 for _ in range(N)] for _ in range(N)]
for _ in range(M):
u, v, w = map(int, input().split())
u -= 1 # 0-indexed にする
v -= 1
distance[u][v] = w
distance[v][u] = w
for i in range(N):
distance[i][i] = 0
# ワーシャルフロイド法で d(i, j) を求める
for i in range(N):
for j in range(N):
for k in range(N):
distance[j][k] = min(distance[j][k], distance[j][i] + distance[i][k])
# C[i] を求める
C = [0 for i in range(N)]
for i in range(N):
for j in range(N):
C[i] += distance[i][j] > S[i]
# 友好ペアの個数を求める
ans = 0
for i in range(N):
for j in range(i):
ans += distance[i][j] <= min(S[i], S[j]) and C[i] == C[j]
print(ans)
