| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 134992 | wzy | 여행하는 상인 (APIO17_merchant) | C++11 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int N = 105;
const int K = 1005;
#define pii pair<int,int>
#define F first
#define S second
#define pb push_back
#define mp make_pair
typedef long long ll;
int n , m , k;
ll b[N][K] , s[N][K];
ll dist[N][N];
int32_t main(){
scanf("%d%d%d" , &n , &m , &k);
for(int i = 0 ; i < n; i++){
for(int j = 0 ; j < k ; j++){
scanf("%lld%lld" , &b[i][j], & s[i][j]);
if(b[i][j] == -1){
b[i][j] = (ll) 1e9 + (ll) 1e9;
}
if(s[i][j] == -1){
s[i][j] = - (ll) 1e9 - (ll) 1e9;
}
}
}
for(int i = 0 ; i < N ; i ++){
for(int j = 0 ; j < N ; j ++ ){
dist[i][j] = (ll) 1e15;
for(int w = 0 ; w < K ; w ++){
dp[i][j][w] = pii((ll) 1e15 , 1);
}
dp[i][j][k] = pii(0 , 0);
}
dist[i][i] = 0;
}
for(int i = 0 ; i < m ; i ++){
int u , v, x;
scanf("%d%d%d" , &u , & v , &x);
u-- , v--;
dist[u][v] = min(dist[u][v] , (ll) x);
}
for(int i = 0 ; i < n; i ++ ){
for(int j = 0 ; j < n ; j ++){
for(int k = 0 ; k < n ; k ++){
dist[j][k] = min(dist[j][i] + dist[i][k] , dist[j][k]);
}
}
}
long long int ans = 0;
for(int i = 0 ; i < n; i ++){
for(int j = 0 ; j < n ; j ++){
long long int U = dist[i][j] + dist[j][i];
for(int x = 0 ; x < k ; x++){
long long int C = -b[i][x] + s[j][x];
ans = max(ans , C/U);
}
}
}
cout<<ans<<endl;
}