이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int INF = 1e9+1;
int n,m,k;
int dis[101][101], adj[101][101], adj2[101][101], prof[101][101];
int s[101][1001],b[101][1001];
bool check(int c){
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
adj2[i][j] = prof[i][j] - c * adj[i][j];
if(adj[i][j] == INF) adj2[i][j] = c * INF;
}
}
for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ dis[i][j] = adj2[i][j];}}
for(int x = 1; x <= n; x++){
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
if(dis[i][x] < c * INF && dis[x][j] < c * INF) dis[i][j] = min(dis[i][j], dis[i][x] + dis[x][j]);
}
}
}
for(int i = 1; i <= n; i++){
if(dis[i][i] >= 0) return 1;
}
return 0;
}
int32_t 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++){
adj[i][j] = INF;
}
}
for(int i = 0; i < m; i++){
int u,v,w;
cin>>u>>v>>w;
adj[u][v] = w;
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
for(int x = 0; x < k; x++){
if(s[j][x] != -1 && b[i][x] != -1){
prof[i][j] = max(prof[i][j], s[j][x] - b[i][x]);
}
}
}
}
int ans = -1;
for(int x = 1e9; x > 0; x/=2){
while(ans + x < 1e9 && check(ans+x)) ans+=x;
}
cout<<ans + 1<<'\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... |