제출 #775655

#제출 시각아이디문제언어결과실행 시간메모리
775655gagik_2007여행하는 상인 (APIO17_merchant)C++17
0 / 100
12 ms596 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; #define ff first #define ss second ll ttt; const ll INF=1e18; const ll MOD=1e9+7; const ll N=107; const ll K=1007; ll n,m,k; vector<ll>g[N]; ll b[K][N],s[K][N]; ll maxval[N]; ll dist[N][N]; void floyd_warshall(){ for(int p=1;p<=n;p++){ for(int v=1;v<=n;v++){ for(int u=1;u<=n;u++){ dist[v][u]=min(dist[v][u],dist[v][p]+dist[p][u]); } } } } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); // freopen("output.txt","w",stdout); cin>>n>>m>>k; for(int i=1;i<=n;i++){ for(int j=1;j<=k;j++){ cin>>b[i][j]>>s[i][j]; } } for(int v=1;v<=n;v++){ for(int u=1;u<=n;u++){ dist[v][u]=INF; if(v==u)dist[v][u]=0; } } for(int i=0;i<m;i++){ ll x,y,t; cin>>x>>y>>t; g[x].push_back(y); dist[x][y]=min(dist[x][y],t); } floyd_warshall(); // for(int v=1;v<=n;v++){ // for(int u=1;u<=n;u++){ // cout<<v<<", "<<u<<": "<<dist[v][u]<<endl; // } // } ll ans=0; for(int i=1;i<=k;i++){ if(b[1][i]!=-1){ for(int v=2;v<=n;v++){ maxval[i]=max(maxval[i],(s[v][i]-b[1][i])/(dist[1][v]+dist[v][1])); } ans=max(ans,maxval[i]); } } cout<<ans<<endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...