제출 #263366

#제출 시각아이디문제언어결과실행 시간메모리
263366amoo_safar여행하는 상인 (APIO17_merchant)C++17
100 / 100
152 ms3448 KiB
// Zende bad Shoma nasime faghat ! #include <bits/stdc++.h> #define pb push_back #define F first #define Se second #define all(x) x.begin(), x.end() #define debug(x) cerr << #x << " : " << x << '\n' using namespace std; typedef __int128 ll; typedef long double ld; typedef string str; typedef pair<ll, ll> pll; const ll Mod = 1000000007LL; const int N = 1e2 + 10; const int K = 1e3 + 10; const ll Inf = 2242545357980376863LL; const ll Log = 30; int n, m, k; int B[N][K], S[N][K]; ll dis[N][N], d[N][N]; int pro[N][N]; ll mul(ll A, ll B){ if((Inf + A - 1) / A <= B){ //assert(false); return Inf; } return A * B; } bool Check(ll x){ for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) d[i][j] = (i == j ? Inf : mul(x, dis[i][j]) - pro[i][j]); for(int z = 1; z <= n; z++) for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++) d[i][j] = min(d[i][j], d[i][z] + d[z][j]); if(d[i][i] <= 0) return true; } return false; } int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); memset(dis, 31, sizeof dis); 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]; int u, v, w; for(int i = 1; i <= m; i++){ cin >> u >> v >> w; dis[u][v] = min(dis[u][v], (ll) w); } // Floyd for(int i = 1; i <= n; i++) dis[i][i] = 0; for(int z = 1; z <= n; z++) for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) dis[i][j] = min(dis[i][j], dis[i][z] + dis[z][j]); for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) for(int obj = 1; obj <= k; obj ++) if((S[j][obj] != -1) && (B[i][obj] != -1)) pro[i][j] = max(pro[i][j], S[j][obj] - B[i][obj]); int L = 0, R = 1e9 + 1, mid; while(L + 1 < R){ mid = (L + R) >> 1; if(Check(mid)) L = mid; else R = mid; } 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...