제출 #1014915

#제출 시각아이디문제언어결과실행 시간메모리
1014915idiotcomputer여행하는 상인 (APIO17_merchant)C++11
0 / 100
46 ms3416 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long int #define pb push_back #define sz size #define pii pair<ll,ll> #define f first #define s second const int mxN = 150; const int mxK = 1e3; const ll inf = 1e18; int n,m,k; vector<pii> adj[mxN]; ll d[mxN][mxN]; ll p[mxN][mxN]; pii vals[mxN][mxK]; bool solve(ll x){ ll d2[n][n]; for (int i =0; i < n; i++) for (int j =0; j < n; j++){ d2[i][j] = d[i][j]*x-p[i][j]; } for (int k = 0; k < n; k++) for (int i = 0; i < n; i++) for (int j = 0; j < n; j++){ if (d2[i][k] != inf && d2[k][j] != inf) d2[i][j] = min(d2[i][j],d2[i][k]+d2[k][j]); } for (int i = 0; i < n; i++) for (int j = 0; j < n; j++){ if (i == j) continue; if (d2[i][j] + d2[j][i] <= 0) return true; } return false; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n >> m >> k; for (int i = 0; i < n; i++) for (int j = 0; j < k; j++) cin >> vals[i][j].f >> vals[i][j].s; for (int i =0; i < n; i++){ for (int j =0; j < n; j++) d[i][j] = inf; d[i][i] = 0; } int v,w,t; for (int i = 0; i < m; i++){ cin >> v >> w >> t; v -= 1; w -= 1; adj[v].pb((pii) {w,t}); d[v][w] = min(d[v][w],(ll)t); } for (int k = 0; k < n; k++) for (int i = 0; i < n; i++) for (int j = 0; j < n; j++){ if (d[i][k] != inf && d[k][j] != inf) d[i][j] = min(d[i][j],d[i][k]+d[k][j]); } /* for (int i =0; i < n; i++){ for (int j =0; j < n; j++) cout << d[i][j] << " "; cout << '\n'; }*/ memset(p,0,sizeof(p)); for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) for (int t = 0; t < k; t++){ if (vals[i][t].f == -1 || vals[j][t].s == -1) continue; p[i][j] = max(p[i][j],vals[j][t].s - vals[i][t].f); } /* for (int i =0; i < n; i++){ for (int j = 0; j < n; j++) cout << p[i][j] << " "; cout << '\n'; } */ ll l = 0; ll r = 1e9+1; ll c; while (r-l>1){ c = (l+r)/2; if (solve(c)) l = c; else r = c; } cout << l << "\n"; 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...