Submission #533461

#	Time	Username	Problem	Language	Result	Execution time	Memory
533461		ohohorz	Travelling Merchant (APIO17_merchant)	C++14	0 / 100	15 ms	1868 KiB

merchant

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define f first
// #define s second
#define mp make_pair
#define pb push_back
#define sz(x) (int)x.size()
#define vi vector<int>

const int N = 100 + 5;
const int INF = 1e18;
const int MOD = 998244353;
const int BLOCKSZ = 318;
const int K = 1005;

int binpow(int a, int b){
    if(b == 0) return 1;
    if(b%2==0){
        int x = binpow(a, b >> 1LL);
        return (x%MOD*x%MOD)%MOD;
    }
    int x = binpow(a, b - 1);
    return (x%MOD*a%MOD)%MOD;
}
int b[N][K], s[N][K],dist[N][N];

void solve(){
    
    int n, m, k;
    cin >> n >> m >> k;
    for(int i =1;i<=n;i++){
        for(int j =1;j<=k;j++) cin >> b[i][j];
        for(int j =1;j<=k;j++) cin >> s[i][j];
    }
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=n;j++){
            dist[i][j] = INF;
        }
        dist[i][i] = 0;
    }
    for(int i =1;i<=m;i++){
        int u, v, d;
        cin >> u >> v >> d;
        dist[u][v] = d;
    }
    for(int k = 1;k <= n;k++){
        for(int i = 1;i <= n;i++){
            for(int j = 1;j <= n;j++){
                if(dist[i][k] < INF and dist[k][j] < INF)
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }

    pii best;// {profit, path length}
    best = mp(-INF, -INF);
    bool first = 1;
    for(int i = 2;i <= n;i++){
        if(dist[1][i] == INF or dist[i][1] == INF) continue;

        int path = dist[1][i] + dist[i][1];

        int profit = -INF;
        for(int j =1;j<=k;j++){
            if(s[i][j] != -1 and b[1][j] != -1)
                profit = max(s[i][j] - b[1][j], profit);
        }
        if(profit == -INF) continue;

        if(first == 1){
            best = mp(profit, path);
            first =0;
        }else{
            if((profit * best.second) > (path * best.first))
                best = mp(profit, path);
        }
    }

    for(int i = 2;i <= n;i++){
        if(dist[1][i] == INF or dist[i][1] == INF) continue;
        int path = dist[1][i] + dist[i][1];
        int profit = -INF;
        for(int j = 1;j <= k;j++){
            if(s[1][j] != -1 and b[1][j] != -1)
                profit = max(profit, s[1][j] - b[1][j]);
        }
        if(first == 1){
            best = mp(profit, path);
            first =0;
        }else{
            if((profit * best.second) > (path * best.first))
                best = mp(profit, path);
        }
    }

    if(first == 1) cout << 0 << "\n";
    else cout << (best.f / best.second) << "\n";




}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(0);
    
    int tc=1;
    // cin >> tc;
    while(tc--){
        solve();
    }

    
    

}
/*
4 5 1
5 4
-1 6
-1 100
-1 5
1 2 3
2 3 3
1 4 1
4 3 1
3 1 1
*/

/*
3 3 2
3 -1 10 10
*/

• Subtask 1: 0 / 12
• Subtask 2: 0 / 21
• Subtask 3: 0 / 33
• Subtask 4: 0 / 34