제출 #625970

#제출 시각아이디문제언어결과실행 시간메모리
625970socpite여행하는 상인 (APIO17_merchant)C++14
100 / 100
428 ms6076 KiB
#include<bits/stdc++.h> using namespace std; #define f first #define s second typedef long long ll; const int maxn = 1005; const ll inf = 1e18; ll w[maxn][maxn], d[maxn][maxn], d2[maxn][maxn], best[maxn][maxn], prc[2][maxn][maxn]; int n, m, K; bool chk(ll x){ for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ if(d[i][j] < inf){ d2[i][j] = d[i][j]*x - best[i][j]; d2[i+n][j+n] = d2[i][j]; if(i != j){ d2[i+n][j] = d2[i][j]; d2[i][j+n] = d2[i][j]; } else{ d2[i+n][j] = inf; d2[i][j+n] = inf; } } else { d2[i][j] = inf; d2[i][j+n] = inf; d2[i+n][j] = inf; d2[i+n][j+n] = inf; } } } for(int k = 1; k <= 2*n; k++){ for(int i = 1; i <= 2*n; i++){ for(int j = 1; j <= 2*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 = 1; i <= n; i++){ //cout << x << " " << i << " " << d2[i][i+n] << endl; if(d2[i][i+n] <= 0)return 1; } return 0; } int main(){ cin >> n >> m >> K; for(int i = 1; i <= n; i++){ for(int j = 1; j <= K; j++){ for(int l = 0; l < 2; l++)cin >> prc[l][i][j]; } } for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++)d[i][j] = i == j ? 0 : inf; } for(int i = 0; i < m; i++){ ll a, b, w; cin >> a >> b >> w; d[a][b] = min(d[a][b], w); } for(int k = 1; k <= n; k++){ for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++)d[i][j] = min(d[i][j], d[i][k]+d[k][j]); } } for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ if(d[i][j] < inf){ for(int l = 1; l <= K; l++){ if(prc[0][i][l] >= 0 && prc[1][j][l] > 0)best[i][j] = max(best[i][j], prc[1][j][l] - prc[0][i][l]); } } } } ll l = 0, r = 1e9; while(l < r){ ll mid = (l+r+1)>>1; if(chk(mid))l = mid; else r = mid-1; } cout << l; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...