제출 #944830

#제출 시각아이디문제언어결과실행 시간메모리
944830Darren0724여행하는 상인 (APIO17_merchant)C++17
100 / 100
64 ms4612 KiB
#include<bits/stdc++.h> using namespace std; #define int long long #define all(x) x.begin(),x.end() #define abcorz ios_base::sync_with_stdio(false);cin.tie(0); const int N=105; const int M=10005; const int INF=1.05e9; const int mod=1e9+7; int n,m,k; vector<int> v[N]; vector<int> a(M),b(M),c(M); vector dis(N,vector(N,INF)); vector adj(N,vector<int>(N,0)); inline void chmin(int &a,int b){ a=(a>b?b:a); } void run(){ for(int k=1;k<=n;k++){ for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ chmin(dis[i][j],dis[i][k]+dis[k][j]); } } } } int solve(int t){ vector<vector<int>> dis1(n+1,vector<int>(n+1,INF)); for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ if(i==j||dis[i][j]==INF)continue; dis1[i][j]=dis[i][j]*t-adj[i][j]; } } for(int k=1;k<=n;k++){ for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ chmin(dis1[i][j],dis1[i][k]+dis1[k][j]); } } } int flag=0; for(int i=1;i<=n;i++){ flag|=(dis1[i][i]<=0); } return flag; } int32_t main(){ abcorz; cin>>n>>m>>k; for(int i=1;i<=n;i++){ for(int j=0;j<k*2;j++){ int p;cin>>p; v[i].push_back(p); } } for(int i=0;i<m;i++){ cin>>a[i]>>b[i]>>c[i]; dis[a[i]][b[i]]=c[i]; } run(); for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ int mx=0; for(int k1=0;k1<k;k1++){ if(v[j][k1*2+1]!=-1&&v[i][k1*2]!=-1){ mx=max(mx,v[j][k1*2+1]-v[i][k1*2]); } } adj[i][j]=mx; } } int l=0,r=INF; while(r-l>1){ int mid=(l+r)>>1; if(solve(mid))l=mid; else r=mid; } cout<<l<<endl; 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...