제출 #754793

#제출 시각아이디문제언어결과실행 시간메모리
754793MISM06여행하는 상인 (APIO17_merchant)C++14
100 / 100
132 ms2172 KiB
//0 1 1 0 1 //0 1 0 0 1 //1 0 0 1 1 //0 1 1 0 1 #include <bits/stdc++.h> #pragma GCC optimize("Ofast,unroll-loops") #pragma GCC target("avx2") using namespace std; #define F first #define S second #define pb push_back #define sze size() #define all(x) x.begin() , x.end() #define wall__ cout << "--------------------------------------\n"; #define kids int mid = (tl + tr) >> 1, cl = v << 1, cr = v << 1 | 1 #define file_io freopen("input.cpp", "r", stdin); freopen("output.cpp", "w", stdout); typedef long long ll; typedef long double dl; typedef pair < int , int > pii; typedef pair < int , ll > pil; typedef pair < ll , int > pli; typedef pair < ll , ll > pll; typedef pair < int , pii > piii; typedef pair < ll, pll > plll; const ll N = 1e2 + 10, K = 1e3 + 10; const ll mod = 1e9 + 7; const ll inf = 1e18; const ll rinf = -2e16; const ll INF = 1e9 + 10; const ll rINF = -1e9 - 10; const ll lg = 32; int n, m, k; ll b[N][K], s[N][K], dis[N][N], pf[N][N], dist[N]; int st[N], en[N], timer, g[N][N]; bool dfs (int v, int p) { st[v] = ++timer; bool res = 0; for (int u = 0; u <= n; u++) { if (g[v][u] == 0) continue; if (st[u] == 0) res |= dfs(u, v); else if (en[u] == 0) return true; } en[v] = timer; return res; } inline bool check (ll mean) { fill(dist, dist + (n + 1), 0); ll ch = inf / mean; for (int k = 1; k < n; k++) { for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (i == j || dis[i][j] >= inf) continue; ll w = pf[i][j] - (mean * min(ch, dis[i][j])); w *= -1; if (dist[i] + w < dist[j]) dist[j] = dist[i] + w; } } } for (int i = 1; i <= n; i++) { if (dist[0] < dist[i]) return 1; if (dist[0] == dist[i]) g[0][i] = 1; else g[0][i] = 0; } st[0] = en[0] = 0; for (int i = 1; i <= n; i++) { st[i] = en[i] = 0; for (int j = 1; j <= n; j++) { if (i == j || dis[i][j] >= inf) { g[i][j] = 0; continue; } ll w = pf[i][j] - (mean * min(ch, dis[i][j])); w *= -1; if (dist[i] + w < dist[j]) return 1; if (dist[i] + w == dist[j]) g[i][j] = 1; else g[i][j] = 0; } } return dfs(0, -1); } void solve () { cin >> n >> m >> k; for (int i = 1; i <= n; i++) { for (int j = 1; j <= k; j++) { cin >> b[i][j] >> s[i][j]; } } for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) dis[i][j] = inf; } for (int i = 1; i <= m; i++) { int v, u, w; cin >> v >> u >> w; dis[v][u] = w; } for (int k = 1; k <= n; k++) { for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]); } } } for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { pf[i][j] = 0; for (int x = 1; x <= k; x++) if (s[j][x] != -1 && b[i][x] != -1) pf[i][j] = max(pf[i][j], s[j][x] - b[i][x]); } } ll l = 0, r = 1e15, mid; while (r - l > 1) { mid = (r + l) / 2ll; if (check(mid)) l = mid; else r = mid; } cout << l << '\n'; } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t = 1; // cin >> t; while (t--) {solve();} return 0; } /* 4 5 2 10 9 5 2 6 4 20 15 9 7 10 9 -1 -1 16 11 1 2 3 2 3 3 1 4 1 4 3 1 3 1 1 */ //shrek will AC this;
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...