제출 #73355

#제출 시각아이디문제언어결과실행 시간메모리
73355FedericoS여행하는 상인 (APIO17_merchant)C++14
12 / 100
100 ms2868 KiB
#include <iostream> using namespace std; int INF=1e9; int N,M,K; int x,y; int C[100][1005][2]; int D[105][105]; int P[105][105]; int main(){ cin>>N>>M>>K; for(int i=0;i<N;i++) for(int j=0;j<K;j++) cin>>C[i][j][0]>>C[i][j][1]; for(int i=0;i<N;i++) for(int j=0;j<N;j++) D[i][j]=(i==j)?0:INF; for(int i=0;i<M;i++) cin>>x>>y>>D[x-1][y-1]; for(int k=0;k<N;k++) for(int i=0;i<N;i++) for(int j=0;j<N;j++) D[i][j]=min(D[i][j],D[i][k]+D[k][j]); for(int a=0;a<N;a++) for(int b=0;b<N;b++) for(int j=0;j<K;j++) if(C[a][j][0]!=-1 and C[b][j][1]!=-1) P[a][b]=max(P[a][b],C[b][j][1]-C[a][j][0]); int ans=0; for(int i=1;i<N;i++) ans=max(ans,(P[0][i]+P[i][0])/(D[0][i]+D[i][0])); cout<<ans; } /*for(int a=0;a<N;a++) for(int b=0;b<N;b++) cout<<a<<" "<<b<<" "<<P[a][b]<<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...