제출 #748670

#제출 시각아이디문제언어결과실행 시간메모리
748670snpmrnhlol여행하는 상인 (APIO17_merchant)C++17
100 / 100
87 ms4252 KiB
#include <iostream> using namespace std; typedef long long ll; const ll N = 1e2,K = 1e3; const ll inf = 1e9; ll b[N][K],s[N][K],d[N][N]; ll p[N][N],p2[N][N]; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); ll n,m,k,i,j,u,w,x,l; cin>>n>>m>>k; for(i = 0;i < n;i++){ for(j = 0;j < n;j++)d[i][j] = inf; for(j = 0;j < k;j++){ cin>>b[i][j]>>s[i][j]; } } for(i = 0;i < m;i++){ cin>>u>>w>>x;w--;u--; d[u][w] = x; } for(i = 0;i < n;i++){ for(j = 0;j < n;j++){ for(l = 0;l < n;l++){ d[j][l] = min(d[j][l],d[j][i] + d[i][l]); } } } for(i = 0;i < n;i++){ for(j = 0;j < n;j++){ for(l= 0;l < k;l++){ if(b[i][l] == -1 || s[j][l] == -1)continue; p2[i][j] = max(p2[i][j],s[j][l] - b[i][l]); } } } ll lef = 0,r = inf; while(lef != r){ ll mij = (lef + r + 1)/2; for(i = 0;i < n;i++){ for(j = 0;j < n;j++){ p[i][j] = -d[i][j]*mij + p2[i][j]; } } for(i = 0;i < n;i++){ for(j = 0;j < n;j++){ for(l = 0;l < n;l++){ p[j][l] = max(p[j][l],p[j][i] + p[i][l]); } } } bool ok = 0; for(i = 0;i < n;i++)if(p[i][i] >= 0){ ok = 1; } if(ok)lef = mij; else r = mij - 1; } cout<<lef; 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...