제출 #899229

#제출 시각아이디문제언어결과실행 시간메모리
899229AdamGS여행하는 상인 (APIO17_merchant)C++17
100 / 100
103 ms4432 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; #define st first #define nd second #define rep(a, b) for(int a = 0; a < (b); ++a) #define pb push_back #define all(a) a.begin(), a.end() const int LIM=107; const ll INF=1e18+7; ll kraw[LIM][LIM], B[LIM][10*LIM], S[LIM][10*LIM], n, k; ll zysk[LIM][LIM], odl[LIM][LIM], tmp[LIM][LIM]; ll dist[LIM], wrz; void poteguj() { rep(i, 20) { rep(i, n) rep(j, n) { tmp[i][j]=odl[i][j]; rep(l, n) if(odl[i][l]!=-INF && odl[l][j]!=-INF) { tmp[i][j]=max(tmp[i][j], min(INF, odl[i][l]+odl[l][j])); } } rep(i, n) rep(j, n) odl[i][j]=tmp[i][j]; } } bool cykl(ll x) { rep(i, n) dist[i]=-INF; dist[x]=0; while(true) { ll ma=-INF, ind=-1; rep(i, n) if(dist[i]>ma && dist[i]<INF) { ma=dist[i]; ind=i; } if(ind==-1) break; ll o=dist[ind]; dist[ind]=INF; if(o+odl[ind][x]>=0) return true; rep(i, n) { if(dist[i]<INF && dist[i]<o+odl[ind][i]) { dist[i]=o+odl[ind][i]; dist[i]=min(dist[i], INF-1); } } } return false; } bool f(ll x) { rep(i, n) rep(j, n) { if(kraw[i][j]==-INF) odl[i][j]=-INF; else { odl[i][j]=kraw[i][j]*x; if(zysk[i][j]>=0) odl[i][j]+=zysk[i][j]; } } rep(i, n) rep(j, n) odl[i][j]*=-1; rep(k, n) rep(i, n) rep(j, n) if(odl[i][k]<INF && odl[k][j]<INF) { odl[i][j]=min(odl[i][j], odl[i][k]+odl[k][j]); } rep(i, n) if(odl[i][i]<=0) return true; return false; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int m; cin >> n >> m >> k; rep(i, n) rep(j, n) kraw[i][j]=-1; rep(i, n) rep(j, k) cin >> B[i][j] >> S[i][j]; rep(i, m) { ll a, b, c; cin >> a >> b >> c; --a; --b; if(kraw[a][b]==-1) kraw[a][b]=c; kraw[a][b]=min(kraw[a][b], c); } rep(i, n) rep(j, n) { zysk[i][j]=-INF; rep(l, k) if(i!=j && B[i][l]!=-1 && S[j][l]!=-1) { zysk[i][j]=max(zysk[i][j], S[j][l]-B[i][l]); } } rep(i, n) rep(j, n) if(kraw[i][j]==-1) odl[i][j]=-INF; else odl[i][j]=-kraw[i][j]; poteguj(); rep(i, n) rep(j, n) kraw[i][j]=odl[i][j]; ll po=0, ko=1000000000; while(po<ko) { ll sr=(po+ko+1)/2; if(f(sr)) po=sr; else ko=sr-1; } cout << po << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...