#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 110;
const int Maxn = 1100;
const ll inf = 1e15;
const ll M = 1e9;
const int sq = 450;
#define debug(x) cerr << "(" << (#x) << "): " << (x) << endl
#define lc (id << 1)
#define rc (lc | 1)
#define all(x) x.begin(), x.end()
#define SZ(x) x.size()
vector<pii> edg[N];
ll dis[N], dp[N][N][2], bs[N][N], a[N][Maxn][2];
int n, q;
bool mark[N];
void min_dis(){
///// Base:
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
dp[i][j][0] = dp[i][j][1] = (i != j) * inf;
for(int v = 0; v < n; v++)
for(pii p: edg[v])
dp[v][p.first][0] = p.second;
////// Update:
for(int k = 0; k < n; k++)
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
dp[i][j][1 - k & 1] = min(dp[i][j][k & 1], dp[i][k][k & 1] + dp[k][j][k & 1]);
}
void best_sell(){
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
for(int k = 0; k < q; k++)
if(a[i][k][0] > 0 && a[j][k][1] > 0)
bs[i][j] = max(bs[i][j], -a[i][k][0] + a[j][k][1]);
}
bool check(ll x){
// c / l > x; c > x * l x * l - c < 0;
for(pii p: edg[0]) mark[p.first] = 1;
for(int i = 0; i < n; i++) if(!mark[i]) edg[0].push_back({i, inf});
for(int i = 0; i < n; i++) dis[i] = inf;
for(int i = 1; i < n; i++)
for(int v = 0; v < n; v++)
for(int u = 0; u < n; u++)
if(dp[u][v][n & 1] <= inf)
dis[v] = min(dis[v], dis[u] + x * dp[u][v][n & 1] - bs[u][v]);
for(int v = 0; v < n; v++)
for(int u = 0; u < n; u++)
if(dp[v][u][n & 1] <= inf){
long double mn = dis[v] + x * dp[v][u][n & 1] - bs[v][u];
if(mn < dis[u]) return 1;
}
return 0;
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(0);
int m; cin>> n>> m>> q;
for(int i = 0; i < n; i++)
for(int j = 0; j < q; j++) cin>> a[i][j][0] >> a[i][j][1];
for(int i = 0; i < m; i++){
int x, y, w; cin>> x>> y>> w;
edg[x - 1].push_back({y - 1, w});
}
min_dis();
best_sell();
ll l = -1, r = 1e9 + 100;
while(r - l > 1){
ll mid = (l + r) >> 1;
(check(mid)? l: r) = mid;
}
cout<< r;
return 0;
}
Compilation message
merchant.cpp: In function 'void min_dis()':
merchant.cpp:34:16: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
34 | dp[i][j][1 - k & 1] = min(dp[i][j][k & 1], dp[i][k][k & 1] + dp[k][j][k & 1]);
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
66 ms |
2440 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
48 ms |
1116 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
