이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
using namespace std;
typedef long long ll;
const ll INF = 1e10;
const int MAX_N = 100 + 9;
const int MAX_K = 1000 + 9;
int n, m, K;
ll buy[MAX_N][MAX_K], sell[MAX_N][MAX_K];
ll w[MAX_N][MAX_N], dist[MAX_N][MAX_N], profit[MAX_N][MAX_N];
ll g[MAX_N][MAX_N], g2[MAX_N][MAX_N];
void read(){
cin >> n >> m >> K;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= K; j++)
cin >> buy[i][j] >> sell[i][j];
for(int i = 0; i < m; i++){
int u, v;
ll w;
cin >> u >> v >> w;
dist[u][v] = w;
}
}
void init(){
for(int i = 1; i < MAX_N; i++)
for(int j = 1; j < MAX_N; j++)
dist[i][j] = INF;
}
void floyd(){
for(int k = 1; k <= n; k++)
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
bool check(ll rat){
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
g[i][j] = -INF;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
if(dist[i][j] < INF)
g[i][j] = max(g[i][j], profit[i][j] - dist[i][j] * rat);
for(int k = 1; k <= n; k++)
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++){
g[i][j] = max(g[i][j], g[i][k] + g[k][j]);
if(g[i][i] >= 0)
return true;
}
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
g2[i][j] = g[i][j];
for(int k = 1; k <= n; k++)
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++){
g2[i][j] = max(g2[i][j], g2[i][k] + g2[k][j]);
if(g2[i][j] > g[i][j])
return true;
}
return false;
}
void solve(){
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
for(int k = 1; k <= K; k++)
if(sell[j][k] == -1 || buy[i][k] == -1)
continue;
else
profit[i][j] = max(profit[i][j], sell[j][k] - buy[i][k]);
ll lo = 0, hi = 1e18, mid, ans = 0;
while(lo <= hi){
mid = (lo + hi) / 2;
if(check(mid)){
ans = mid;
lo = mid + 1;
} else
hi = mid - 1;
}
cout << ans << '\n';
}
int main()
{
init();
read();
floyd();
solve();
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... |