#include <iostream>
using namespace std;
#include <vector>
#define vi vector<int>
#define ll long long
#include <algorithm>
#include <set>
#include <string>
#include <bitset>
#include <cmath>
#include <math.h>
#define pll pair<ll,ll>
#define vll vector<ll>
#define pi pair<int,int>
#include <map>
#include <queue>
#define x first
#define y second
#define pd pair<double,double>
const int siz = 101;
const int MK = 1001;
ll dis[siz][siz];
ll pro[siz][siz];
ll pr[siz][2*MK];
int main()
{
int n, m, K;
cin >> n >> m >> K;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i != j)dis[i][j] = 1e18;
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < 2 * K; j++) {
cin >> pr[i][j];
if (pr[i][j] == -1) {
if (j % 2)pr[i][j] = -1e18;
else pr[i][j] = 1e18;
}
}
}
for (int i = 0; i < m; i++) {
ll a, b, c;
cin >> a >> b >> c;
a--, b--;
dis[a][b] = min(dis[a][b],c);
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < n; k++) {
dis[j][k] = min(dis[j][k], dis[j][i] + dis[i][k]);
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < 2*K; k+=2) {
pro[i][j] = max(pro[i][j], -pr[i][k] + pr[j][k + 1]);
}
}
}
int l = 0, r=1e9;
while (l < r) {
int mid = (l + r+1) / 2;
// is it possible that profit/dis >= mid <--> mid*dis - profit <= 0?
vector<vll> procur(n, vll(n,1e18));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < n; k++) {
procur[i][j] = min(procur[i][j], mid * (dis[i][k] + dis[k][j]) - pro[k][j]);
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if(i!=j)procur[i][j] = 200 * procur[i][j] - 1;
}
}
vll dp(n,1e18);
dp[0] = 0;
bool f = 0;
for (int it = 0; it <= n; it++) {
vll dpt= dp;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (it == n && dpt[i] > dp[j] + procur[j][i])f = 1;
dpt[i] = min(dpt[i], dp[j] + procur[j][i]);
}
}
dp = dpt;
}
if (f == 1) {
l = mid;
}
else {
r = mid-1;
}
}
cout << l;
}
// Run program: Ctrl + F5 or Debug > Start Without Debugging menu
// Debug program: F5 or Debug > Start Debugging menu
// Tips for Getting Started:
// 1. Use the Solution Explorer window to add/manage files
// 2. Use the Team Explorer window to connect to source control
// 3. Use the Output window to see build output and other messages
// 4. Use the Error List window to view errors
// 5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
// 6. In the future, to open this project again, go to File > Open > Project and select the .sln file
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
131 ms |
3408 KB |
Output is correct |
2 |
Correct |
77 ms |
1060 KB |
Output is correct |
3 |
Correct |
79 ms |
1060 KB |
Output is correct |
4 |
Correct |
11 ms |
604 KB |
Output is correct |
5 |
Correct |
11 ms |
604 KB |
Output is correct |
6 |
Correct |
11 ms |
748 KB |
Output is correct |
7 |
Correct |
12 ms |
604 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
11 ms |
604 KB |
Output is correct |
10 |
Correct |
11 ms |
752 KB |
Output is correct |
11 |
Correct |
11 ms |
604 KB |
Output is correct |
12 |
Correct |
1 ms |
344 KB |
Output is correct |
13 |
Correct |
12 ms |
604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
748 KB |
Output is correct |
2 |
Correct |
12 ms |
604 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
11 ms |
604 KB |
Output is correct |
5 |
Correct |
11 ms |
752 KB |
Output is correct |
6 |
Correct |
11 ms |
604 KB |
Output is correct |
7 |
Correct |
1 ms |
344 KB |
Output is correct |
8 |
Correct |
12 ms |
604 KB |
Output is correct |
9 |
Correct |
14 ms |
604 KB |
Output is correct |
10 |
Correct |
13 ms |
604 KB |
Output is correct |
11 |
Correct |
11 ms |
792 KB |
Output is correct |
12 |
Correct |
10 ms |
604 KB |
Output is correct |
13 |
Correct |
12 ms |
604 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Incorrect |
11 ms |
604 KB |
Output isn't correct |
16 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
84 ms |
1116 KB |
Output is correct |
2 |
Correct |
142 ms |
4176 KB |
Output is correct |
3 |
Correct |
82 ms |
1112 KB |
Output is correct |
4 |
Correct |
87 ms |
1372 KB |
Output is correct |
5 |
Correct |
86 ms |
1368 KB |
Output is correct |
6 |
Correct |
83 ms |
1112 KB |
Output is correct |
7 |
Correct |
12 ms |
600 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
12 ms |
608 KB |
Output is correct |
10 |
Correct |
12 ms |
604 KB |
Output is correct |
11 |
Incorrect |
14 ms |
616 KB |
Output isn't correct |
12 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
604 KB |
Output is correct |
2 |
Correct |
13 ms |
604 KB |
Output is correct |
3 |
Correct |
11 ms |
792 KB |
Output is correct |
4 |
Correct |
10 ms |
604 KB |
Output is correct |
5 |
Correct |
12 ms |
604 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Incorrect |
11 ms |
604 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |