제출 #674912

#제출 시각아이디문제언어결과실행 시간메모리
674912Cookie여행하는 상인 (APIO17_merchant)C++14
100 / 100
117 ms4220 KiB
#include<bits/stdc++.h> using namespace std; #include<fstream> #define ll long long #define vt vector #define pb push_back #define fi first #define se second #define forr(i, a, b) for(int i = a; i < b; i++) #define dorr(i, a, b) for(int i = a; i >= b; i--) typedef unsigned long long ull; #define pii pair<int, int> #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") const ll mod= 1e9 + 7; const int mxk = 1e3, sq = 750, mxn = 105; ll best[mxn + 1][mxn + 1], d[mxn + 1][mxn + 1], s[mxn + 1][mxk + 1], b[mxn + 1][mxk + 1], dis[mxn + 1][mxn + 1]; int n, m, k; struct e{ ll u, v, w; }; vt<e>edge; bool ck(ll mid){ for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ if(dis[i][j] == 1e18)d[i][j] = 1e18; else d[i][j] = dis[i][j] * mid - best[i][j]; } } for(int l = 1; l <= n; l++){ for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ if(d[i][l] != 1e18 && d[l][j] != 1e18){ d[i][j] = min(d[i][j], d[i][l] + d[l][j]); } } } } for(int i = 1; i <= n; i++){ if(d[i][i] <= 0)return(true); } return(false); } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); 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] = 1e18; } forr(i, 0, m){ int u, v, w; cin >> u >> v >> w; dis[u][v] = w; } for(int l = 1; l <= n; l++){ for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ dis[i][j] = min(dis[i][j], dis[i][l] + dis[l][j]); } } } for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ //if(i == j)continue; for(int l = 1; l <= k; l++){ if(s[j][l] == -1 || b[i][l] == -1)continue; best[i][j] = max(best[i][j], s[j][l] - b[i][l]); } } } ll l = 1, r = 1e9, ans = 0; while(l <= r){ ll mid = l + (r - l) / 2; if(ck(mid)){ ans = mid; l = mid + 1; }else{ r = mid - 1; } } cout << ans; 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...