oj.uz

답안 #745109

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
745109 2023-05-19T12:06:54 Z Trunkty 여행하는 상인 (APIO17_merchant) C++14
0 / 100
 24 ms 3380 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll

int n,m,k;
int store[105][1005][2];
int dist[105][105],prof[105][105];
int best[105][105][2];

signed main(){
    ios::sync_with_stdio(false);
	cin.tie(NULL);
    cin >> n >> m >> k;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=k;j++){
            cin >> store[i][j][0] >> store[i][j][1];
            if(store[i][j][0]==-1){
                store[i][j][0] = 2e9;
            }
            if(store[i][j][1]==-1){
                store[i][j][1] = -1;
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i!=j){
                dist[i][j] = 2e18;
            }
        }
    }
    for(int i=1;i<=m;i++){
        int a,b,c;
        cin >> a >> b >> c;
        dist[a][b] = c;
    }
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j]);
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            prof[i][j] = -2e9;
            for(int k=1;k<=n;k++){
                prof[i][j] = max(prof[i][j],store[i][k][1]-store[j][k][0]);
            }
        }
    }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                best[i][j][0] = prof[i][j];
                best[i][j][1] = dist[i][j];
            }
        }
        for(int k=1;k<=n;k++){
            for(int i=1;i<=n;i++){
                for(int j=1;j<=n;j++){
                    if(best[i][j][1]==0){
                        best[i][j][0] = best[i][k][0]+best[k][j][0];
                        best[i][j][1] = best[i][k][1]+best[k][j][1];
                    }
                    else{
                        if(best[i][k][1]+best[k][j][1]==0){
                            continue;
                        }
                        int a = best[i][k][0]+best[k][j][0], b = best[i][k][1]+best[k][j][1];
                        if(a*best[i][j][1]>b*best[i][j][0]){
                            best[i][j][0] = a;
                            best[i][j][1] = b;
                        }
                    }
                }
            }
        }
    int ans=0;
    for(int i=1;i<=n;i++){
        if(best[i][i][1]){
        ans = max(ans,best[i][i][0]/best[i][i][1]);
        }
    }
    cout << ans << "\n";
    return 0;
}

Subtask #1
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 24 ms 3380 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 724 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 10 ms 1364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 724 KB Output isn't correct
2 Halted 0 ms 0 KB -