제출 #544898

#제출 시각아이디문제언어결과실행 시간메모리
544898zaneyu여행하는 상인 (APIO17_merchant)C++14
100 / 100
123 ms3764 KiB
/*input 4 5 2 10 9 5 2 6 4 20 15 9 7 10 9 -1 -1 16 11 1 2 3 2 3 3 1 4 1 4 3 1 3 1 1 */ #include<bits/stdc++.h> using namespace std; #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; typedef tree<long long,null_type,less_equal<long long>,rb_tree_tag,tree_order_statistics_node_update> indexed_set; #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("bmi,bmi2,lzcnt,popcnt") //order_of_key #of elements less than x // find_by_order kth element using ll=long long; using ld=long double; using pii=pair<ll,ll>; #define f first #define s second #define pb push_back #define REP(i,n) for(ll i=0;i<n;i++) #define REP1(i,n) for(ll i=1;i<=n;i++) #define FILL(n,x) memset(n,x,sizeof(n)) #define ALL(_a) _a.begin(),_a.end() #define sz(x) (int)x.size() #define SORT_UNIQUE(c) (sort(c.begin(),c.end()),c.resize(distance(c.begin(),unique(c.begin(),c.end())))) const ll maxn=2e3+5; const ll maxlg=__lg(maxn)+2; const ll INF64=4e18; const int INF=0x3f3f3f3f; const ll MOD=998244353; const ld PI=acos(-1); const ld eps=1e-6; #define lowb(x) x&(-x) #define MNTO(x,y) x=min(x,(__typeof__(x))y) #define MXTO(x,y) x=max(x,(__typeof__(x))y) template<typename T1,typename T2> ostream& operator<<(ostream& out,pair<T1,T2> P){ out<<P.f<<' '<<P.s; return out; } template<typename T> ostream& operator<<(ostream& out,vector<T> V){ REP(i,sz(V)) out<<V[i]<<((i!=sz(V)-1)?" ":""); return out; } ll mult(ll a,ll b){ return a*b%MOD; } ll mypow(ll a,ll b){ a%=MOD; if(a==0) return 0; if(b<=0) return 1; ll res=1LL; while(b){ if(b&1) res=(res*a)%MOD; a=(a*a)%MOD; b>>=1; } return res; } int arr[105][maxn]; int n,m,k; vector<pair<int,pii>> ed; ll dist[105][105]; ll d[105][105]; ll add[105][105]; bool wk(ll mid){ REP(i,n) REP(j,n){ if(d[i][j]==INF64) dist[i][j]=-INF64; else dist[i][j]=add[i][j]-d[i][j]*mid; } REP(k,n) REP(i,n) REP(j,n) MXTO(dist[i][j],dist[i][k]+dist[k][j]); //REP(i,n) REP(j,n) cout<<i<<' '<<j<<' '<<dist[i][j]<<'\n'; REP(i,n) if(dist[i][i]>=0){ return true; } return false; } int32_t main(){ ios::sync_with_stdio(false),cin.tie(0); cin>>n>>m>>k; REP(i,n) REP(j,2*k) cin>>arr[i][j]; REP(i,n) REP(j,n) d[i][j]=INF64; REP(i,m){ int a,b,c; cin>>a>>b>>c; --a,--b; ed.pb({c,{a,b}}); d[a][b]=c; } REP(k,n) REP(i,n) REP(j,n) MNTO(d[i][j],d[i][k]+d[k][j]); //REP(i,n) REP(j,n) cout<<i<<' '<<j<<' '<<d[i][j]<<'\n'; REP(i,n){ REP(j,n){ add[i][j]=0; REP(a,k){ if(arr[i][a*2]!=-1 and arr[j][a*2+1]!=-1) MXTO(add[i][j],arr[j][a*2+1]-arr[i][a*2]); } //cout<<i<<' '<<j<<' '<<add[i][j]<<'\n'; } } ll l=0,r=INF; while(l<r){ ll mid=(l+r+1)/2; if(wk(mid)) l=mid; else r=mid-1; } cout<<l; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...