Submission #1260052

#TimeUsernameProblemLanguageResultExecution timeMemory
1260052hamanp87Travelling Merchant (APIO17_merchant)C++20
100 / 100
48 ms2116 KiB
#include<bits/stdc++.h> using namespace std; using ll=long long; //#pragma GCC optimize("03,unroll-loops") //#pragma GCC target("avx2") //#pragma GCC target("sse4") #define all(v) v.begin(),v.end() #define F first #define S second #define pub push_back #define pob pop_back #define puf push_front #define pof pop_front //#define randi uniform_int_distribution<long long> #define damoon(v) v.resize(unique(all(v))-v.begin()) //mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); //randi dist(0,10000000000000000); typedef pair<int,int> pii; typedef pair<long long,long long> pll; typedef pair<int,bool> pib; typedef pair<long long,bool> plb; typedef pair<int,pii> pip; typedef pair<pii,int> ppi; typedef vector<int> veci; typedef vector<long long> vecl; typedef vector<bool> vecb; typedef vector<pii> vecp; typedef set<int> seti; typedef set<long long> setl; typedef set<pii> setp; typedef map<int,int> mapii; typedef map<long long,long long> mapll; typedef map<int,bool> mapib; typedef map<long long,bool> maplb; const int mod=1e9+7,neginf=-1e9; const ll inf=LLONG_MAX/4; const double PI=acos(-1); void solve() { int n,m,k; cin>>n>>m>>k; vector<vecl> b(n,vecl(k)); vector<vecl> s(n,vecl(k)); for(int i=0;i<n;i++) for(int j=0;j<k;j++) cin>>b[i][j]>>s[i][j]; vector<vecl> mat(n,vecl(n,inf)); for(int e=0;e<m;e++) { int ai,bi; ll ci; cin>>ai>>bi>>ci; ai--; bi--; mat[ai][bi]=min(mat[ai][bi],ci); } for(int u=0;u<n;u++) for(int i=0;i<n;i++) if(mat[i][u]<inf) for(int j=0;j<n;j++) if(mat[u][j]<inf) mat[i][j]=min(mat[i][j],mat[i][u]+mat[u][j]); vector<vecl> f(n,vecl(n,0)); for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { ll bst=LLONG_MIN/4; for(int x=0;x<k;x++) if(b[i][x]!=-1 and s[j][x]!=-1) bst=max(bst,s[j][x]-b[i][x]); f[i][j]=max(bst,0LL); } } ll L=1,R=1000000000LL,ans=0; vector<vecl> dp(n,vecl(n)); while(L<=R) { ll mid=(L+R)>>1; for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { if(mat[i][j]>=inf) { ll dis=inf/mid; dp[i][j]=mid*dis-f[i][j]; } else { ll dis=min(mat[i][j],inf/mid); dp[i][j]=mid*dis-f[i][j]; } } } for(int x=0;x<n;x++) for(int i=0;i<n;i++) for(int j=0;j<n;j++) dp[i][j]=min(dp[i][j],dp[i][x]+dp[x][j]); bool is=0; for(int i=0;i<n;i++) { if(dp[i][i]<=0) { is=1; break; } } if(is) { ans=mid; L=mid+1; } else { R=mid-1; } } cout<<ans<<"\n"; } int main() { cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false); //ifstream fin("in.txt"); //ofstream fout("out.txt"); int t=1; //cin>>t; while(t--) { solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...