이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll
int N, M, K;
int S[101][1001], B[101][1001];
int D[101][101], G[101][101];
int DP[101][101];
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> N >> M >> K;
for(int l = 1; l <= N; l++)
for(int i = 1; i <= N; i++)
D[l][i] = 1e9 + 7;
for(int l = 1; l <= N; l++)
for(int i = 1; i <= K; i++)
cin >> B[l][i] >> S[l][i];
for(int l = 0; l < M; l++) {
int V, W, T; cin >> V >> W >> T;
D[V][W] = T;
}
for(int l = 1; l <= N; l++)
for(int i = 1; i <= N; i++)
for(int j = 1; j <= K; j++)
if(B[l][j] != -1 && S[i][j] != -1)
G[l][i] = max(G[l][i], S[i][j] - B[l][j]);
for(int l = 1; l <= N; l++)
for(int i = 1; i <= N; i++)
for(int j = 1; j <= N; j++)
D[i][j] = min(D[i][j], D[i][l] + D[l][j]);
int lo = 1, hi = 1e9 + 7, res = 0;
while(lo <= hi) {
int md = (lo + hi) / 2;
for(int l = 1; l <= N; l++)
for(int i = 1; i <= N; i++)
DP[l][i] = md * D[l][i] - G[l][i];
for(int l = 1; l <= N; l++)
for(int i = 1; i <= N; i++)
for(int j = 1; j <= N; j++)
DP[i][j] = min(DP[i][j], DP[i][l] + DP[l][j]);
bool can = false;
for(int l = 1; l <= N; l++)
can |= (DP[l][l] <= 0);
if(can) res = md, lo = md + 1;
else hi = md - 1;
}
cout << res << "\n";
return 0;
}
# | 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... |