#include <bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e18;
const int MAX_N = 100;
const int MAX_K = 1000;
int N,M,K;
vector<vector<int>> adj(MAX_N,vector<int>(MAX_N,INF));
vector<vector<int>> B(MAX_N, vector<int>(MAX_K)), S(MAX_N, vector<int>(MAX_K));
main() {
cin >> N >> M >> K;
for (int i = 0; i < N; i++) {
for (int z = 0; z < K; z++) {
cin >> B[i][z] >> S[i][z];
}
}
for (int i = 0; i < M; i++) {
int V,W,P; cin >> V >> W >> P;
adj[V-1][W-1] = P;
}
auto dist = adj;
for (int k = 0; k < N; k++) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
int ans = 0;
for (int i = 1; i < N; i++) {
int val = 0;
for (int z = 0; z < K; z++) {
val = max(val,S[i][z] - B[0][z]);
}
ans = max(ans,val/(dist[0][i]+dist[i][0]));
}
cout << ans << "\n";
return 0;
}
Compilation message
merchant.cpp:14:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main() {
^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
80 ms |
3312 KB |
Output is correct |
2 |
Correct |
7 ms |
2048 KB |
Output is correct |
3 |
Correct |
4 ms |
2048 KB |
Output is correct |
4 |
Correct |
3 ms |
2048 KB |
Output is correct |
5 |
Correct |
4 ms |
2048 KB |
Output is correct |
6 |
Correct |
4 ms |
2048 KB |
Output is correct |
7 |
Correct |
6 ms |
2048 KB |
Output is correct |
8 |
Correct |
5 ms |
2048 KB |
Output is correct |
9 |
Correct |
4 ms |
2048 KB |
Output is correct |
10 |
Correct |
5 ms |
2048 KB |
Output is correct |
11 |
Correct |
4 ms |
2048 KB |
Output is correct |
12 |
Correct |
6 ms |
2048 KB |
Output is correct |
13 |
Correct |
6 ms |
2048 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
4 ms |
2048 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
15 ms |
2176 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
4 ms |
2048 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |