제출 #491864

#제출 시각아이디문제언어결과실행 시간메모리
491864K4YAN여행하는 상인 (APIO17_merchant)C++17
100 / 100
88 ms4480 KiB
//Be Name Khoda #include<bits/stdc++.h> #pragma GCC target ("avx2,tune=native") using namespace std; #define ll long long #define ld long double #define all(x) x.begin(), x.end() #define pii pair<int, int> #define piii pair<pii, int> #define piiii pair<pii, pii> #define piiiii pair<pii, piii> #define pll pair<ll, ll> #define plll pair<pll, ll> const ll mxn = 116, MXN = 1016; ll n, m, k, q; ll dis[mxn][mxn], f[mxn][mxn], b[mxn][MXN], s[mxn][MXN]; vector<pll> adj[mxn]; bool check(ll x) { ll d[mxn][mxn]; for(int i = 0; i <= n; i++) { for(int j = 0; j <= n; j++) { d[i][j] = -1LL * MXN * MXN * MXN; } } for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { d[i][j] = f[i][j] + -1LL * x * dis[i][j]; } } for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { for(int w = 1; w <= n; w++) { d[j][w] = max(d[j][w], d[j][i] + d[i][w]); } } } for(int i = 1; i <= n; i++) { if(d[i][i] > 0) { return 1; } if(d[i][i] < 0) continue; for(int j = 1; j <= n; j++) { if(d[i][j] + d[j][i] == d[i][i] && i != j) { return 1; } } } return 0; } ll bs(ll l, ll r) { if(r - l == 1) return l; ll mid = (l + r) >> 1; if(check(mid)) { return bs(mid, r); } return bs(l, mid); } void input() { for(int i = 0; i < mxn; i++) { for(int j = 0; j < mxn; j++) { dis[i][j] = 1LL * MXN * MXN * MXN; } dis[i][i] = 0; } cin >> n >> m >> k; for(int i = 1; i <= n; i++) { for(int j = 0; j < k; j++) { cin >> b[i][j] >> s[i][j]; } } for(int i = 0; i < m; i++) { ll v, u; cin >> v >> u >> q; adj[v].push_back({u, q}); dis[v][u] = min(dis[v][u], q); } } void solve() { for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { for(int w = 1; w <= n; w++) { dis[j][w] = min(dis[j][w], dis[j][i] + dis[i][w]); } for(int w = 0; w < k; w++) { if(b[i][w] != -1 && s[j][w] != -1) { f[i][j] = max(f[i][j], s[j][w] - b[i][w]); } } } } cout << bs(0LL, 1LL* MXN * MXN * MXN) << endl; } int main() { ios::sync_with_stdio(false); cin.tie(NULL); input(), solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...