제출 #166470

#제출 시각아이디문제언어결과실행 시간메모리
166470combi1k1여행하는 상인 (APIO17_merchant)C++14
0 / 100
80 ms2676 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long int s[101][1000]; int b[101][1000]; int d[101][101]; int w[101][101]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; int m; cin >> m; int k; cin >> k; for(int i = 0 ; i < n ; ++i) for(int j = 0 ; j < k ; ++j) cin >> b[i][j], cin >> s[i][j]; memset(d,0x3f,sizeof d); for(int i = 0 ; i < n ; ++i) d[i][i] = 0; for(int i = 0 ; i < m ; ++i) { int x; cin >> x; --x; int y; cin >> y; --y; int t; cin >> t; d[x][y] = t; d[y][x] = t; } for(int T = 0 ; T < n ; ++T) for(int i = 0 ; i < n ; ++i) for(int j = 0 ; j < n ; ++j) d[i][j] = min(d[i][j],d[i][T] + d[T][j]); for(int P = 0 ; P < k ; ++P) for(int i = 0 ; i < n ; ++i) for(int j = 0 ; j < n ; ++j) if (b[i][P] >= 0 && s[j][P] >= 0) w[i][j] = max(w[i][j],s[j][P] - b[i][P]); vector<vector<ll> > dd(n,vector<ll>(n)); int l = 0; int r = 1e9 + 7; for(; l < r ;) { m = (l + r + 2) / 2; for(int i = 0 ; i < n ; ++i) for(int j = 0 ; j < n ; ++j) dd[i][j] = 1ll * m * d[i][j] - w[i][j]; for(int T = 0 ; T < n ; ++T) for(int i = 0 ; i < n ; ++i) for(int j = 0 ; j < n ; ++j) dd[i][j] = min(dd[i][j],dd[i][T] + dd[T][j]); bool ok = 0; for(int i = 0 ; i < n ; ++i) if (dd[i][i] < 0) { ok = 1; break; } if (ok) l = m; else r = m - 1; } cout << l << endl; } /* 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 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...