#include <bits/stdc++.h>
using namespace std;
inline void fileIO(string s) {
freopen((s + ".in").c_str(), "r", stdin);
freopen((s + ".out").c_str(), "w", stdout);
}
inline void read() {}
template <class S>
inline void read(S &arg) {
cin >> arg;
}
template <class S>
inline void readA(S Lptr, S Rptr) {
while (Lptr != Rptr) {
read(*Lptr);
Lptr++;
}
}
template <class S, class... T>
inline void read(S &arg, T &... rest) {
read(arg);
read(rest...);
}
inline void write() {}
template <class S>
inline void write(S arg) {
cout << arg;
}
template <class S>
inline void writeA(S Lptr, S Rptr, char del = ' ') {
if (Lptr != Rptr) {
write(*Lptr);
Lptr++;
}
while (Lptr != Rptr) {
write(del);
write(*Lptr);
Lptr++;
}
}
template <class S, class... T>
inline void write(S arg, T... rest) {
write(arg);
write(' ');
write(rest...);
}
#define rep(i, j, k) for (int i = j; i < (int)k; i++)
#define pb push_back
#define mt make_tuple
#define all(x) x.begin(), x.end()
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
template <class T, class S>
inline bool smin(T &a, S b) {
return (T)b < a ? a = b, 1 : 0;
}
template <class T, class S>
inline bool smax(T &a, S b) {
return a < (T)b ? a = b, 1 : 0;
}
constexpr int MOD = 1e9 + 7;
constexpr int N = 110;
constexpr int K = 1010;
template <typename T>
inline T mod(T &v) {
return v = (v % MOD + MOD) % MOD;
}
template <typename S, typename T>
inline S add(S &l, T r) {
return mod(l += r);
}
ll po(ll v, ll u) {
return u ? po(v * v % MOD, u >> 1) * (u & 1 ? v : 1) % MOD : 1;
}
int n , m , k;
ll B[N][K];
ll S[N][K];
ll mat[N][N];
ll dist[N][N];
ll d[N][N], p[2][N];
bitset<N> mark, adj[N];
bool dfs(int v) {
mark[v] = true;
rep(i , 0 , n)
if (adj[v][i]) {
if (mark[i] || (!mark[i] && dfs(i)))
return true;
}
return false;
}
int32_t main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
memset(dist, 63 , sizeof(dist));
read(n , m, k);
rep(i , 0 , n) {
dist[i][i] = 0;
rep(j , 0 , k)
read(B[i][j] , S[i][j]);
}
rep(i , 0 , m) {
int u , v , w;
read(u , v , w);
u--;
v--;
smin(dist[u][v] , w);
}
rep(z , 0 , n)
rep(i , 0 , n)
rep(j , 0 , n)
smin(dist[i][j] , dist[i][z] + dist[z][j]);
rep(i , 0 , n) {
dist[i][i] = dist[N - 1][N - 1];
rep(j , 0 , n)
rep(z , 0 , k)
if (~B[i][z] && ~S[j][z])
smax(mat[i][j] , S[j][z] - B[i][z]);
}
auto f = [](int limit) -> bool {
memset(d , 63 , sizeof(d));
memset(p , 0 , sizeof(p));
rep(i , 0 , n)
rep(j , 0 , n)
if (dist[i][j] != dist[N - 1][N - 1])
d[i][j] = dist[i][j] * limit - mat[i][j];
mark.reset();
rep(shit , 0 , n) {
adj[shit].reset();
rep(i , 0 , n)
rep(j , 0 , n)
if (d[i][j] != d[N - 1][N - 1])
smin(p[1][j] , p[0][i] + d[i][j]);
memcpy(p[0] , p[1] , sizeof(p[1]));
}
rep(i , 0 , n)
rep(j , 0 , n)
if (d[i][j] != d[N - 1][N - 1]) {
if (smin(p[1][j] , p[0][i] + d[i][j]))
return true;
else if (p[1][j] == p[0][i] + d[i][j])
adj[i][j] = true;
}
rep(i , 0 , n)
if (!mark[i])
if (dfs(i))
return true;
return false;
};
int lo = 0, hi = 1e9 + 10;
while (lo != hi - 1) {
int mid = lo + hi >> 1;
if (f(mid))
lo = mid;
else
hi = mid;
}
write(lo);
return 0;
}
Compilation message
merchant.cpp: In function 'int32_t main()':
merchant.cpp:189:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = lo + hi >> 1;
~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
62 ms |
2140 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
1024 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
41 ms |
1536 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
1024 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
