이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <algorithm>
#define long long long
using namespace std;
const int N = 100 + 2;
const int K = 1000 + 2;
const long INF = 1e18;
int n, m, k;
int priceBuy[N][K];
int priceSell[N][K];
long dist[N][N];
long num[N][N], den[N][N];
int main()
{
cin >> n >> m >> k;
for (int i = 1; i <= n; ++i)
for (int j = 0; j < k * 2; ++j)
if (j & 1) cin >> priceSell[i][j / 2];
else cin >> priceBuy[i][j / 2];
for (int i = 1; i <= n; ++i)
{
fill(dist[i] + 1, dist[i] + 1 + n, INF);
dist[i][i] = INF;
}
for (int i = 0; i < m; ++i)
{
int u, v, w; cin >> u >> v >> w;
dist[u][v] = min(dist[u][v], (long) w);
}
// Floyd-Warshall algorithm
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]);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
{
if (i == j) continue;
if (dist[i][j] == INF)
{
num[i][j] = -1;
continue;
}
for (int l = 0; l < k; ++l)
if (priceBuy[i][l] != -1 && priceSell[j][l] != -1 && priceBuy[i][l] < priceSell[j][l])
{
num[i][j] = max(num[i][j], (long) priceSell[j][l] - priceBuy[i][l]);
}
den[i][j] = dist[i][j];
}
for (int l = 1; l <= n; ++l)
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
if (dist[i][l] != INF && dist[l][j] != INF && (i != l || j != l))
{
double old_val = (num[i][j] != -1 && den[i][j] != 0 ? (double) num[i][j] / den[i][j] : 0);
long new_num = num[i][l] + num[l][j];
long new_den = den[i][l] + den[l][j];
double new_val = (new_den != 0 ? (double) new_num / new_den : 0);
if (new_val > old_val)
num[i][j] = new_num, den[i][j] = new_den;
}
double ans = 0;
for (int i = 1; i <= n; ++i)
ans = max(ans, (den[i][i] != 0 ? (double) num[i][i] / den[i][i] : 0));
cout << (long) ans;
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... |