이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define pii pair<int,int>
#define ff first
#define ss second
using namespace std;
const int MAXN = 100;
const int MAXK = 1000;
const int INF = 1e18;
int n, m, K;
int ans;
int B[MAXN+1][MAXK];
int S[MAXN+1][MAXK];
int a, b, c;
int dis[MAXN+1][MAXN+1];
int dp[MAXN+1][MAXN+1];
signed main() {
cin >> n >> m >> K;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < K; j++) {
cin >> B[i][j] >> S[i][j];
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
dis[i][j] = INF;
}
}
for (int i = 0; i < m; i++) {
cin >> a >> b >> c;
dis[a][b] = c;
}
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i == j || dis[i][j] == INF) continue;
for (int k = 0; k < K; k++) {
if (S[j][k] == -1 || B[i][k] == -1) continue;
dp[i][j] = max(dp[i][j], S[j][k] - B[i][k]);
}
}
}
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (dp[i][j] < dp[i][k] + dp[k][j] && dis[i][j] == dis[i][k] + dis[k][j]) {
dp[i][j] = dp[i][k] + dp[k][j];
}
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i == j || dis[i][j] == INF || dis[j][i] == INF) continue;
ans = max(ans, (dp[i][j] + dp[j][i]) / (dis[i][j] + dis[j][i]));
}
}
cout << ans << "\n";
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |