Submission #1116400

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116400		whale_island1	Travelling Merchant (APIO17_merchant)	C++14	0 / 100	54 ms	2120 KiB

merchant

//   __________________
//  | ________________ |
//  ||          ____  ||
//  ||   /\    |      ||
//  ||  /__\   |      ||
//  || /    \  |____  ||
//  ||________________||
//  |__________________|
//  \###################\
//   \###################\
//    \        ____       \
//     \_______\___\_______\
// An AC a day keeps the doctor away.
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#define hutao_my_wife ios_base::sync_with_stdio(0);
#define forcalors_so_cute cin.tie(0);
/*
inline char readchar() noexcept {
    static char buffer[BUFSIZ], * now = buffer + BUFSIZ, * end = buffer + BUFSIZ;
    if (now == end)
    {
        if (end < buffer + BUFSIZ)
            return EOF;
        end = (buffer + fread(buffer, 1, BUFSIZ, stdin));
        now = buffer;
    }
    return *now++;
}
inline int nextint() noexcept {
    int x = 0, c = readchar(), neg = 0;
    while(('0' > c || c > '9') && c!='-' && c!=EOF) c = readchar();
    if(c == '-') neg = true, c = readchar();
    while('0' <= c && c <= '9') x = (x<<3) + (x<<1) + (c^'0'), c = readchar();
    if(neg) x = -x;
    return x; // returns 0 if EOF
}

//fast io cin>>a 改成 a = nextint();
*/
#define ll long long
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define pb push_back
#define eb emplace_back
#define ALL(v) v.begin(), v.end()
#define bug(A) cout<<A<<" hi\n";
using namespace std;

const ll M = 200005;
int g[105][105];
int B[105][1005], S[105][1005], dis[105][105], earn[105][105];
pii dp[105][105];
int n,m,num;
void solve(){
    cin>>n>>m>>num;
    for(int i = 1; i <= n; i++){
        for(int j = 0; j < num; j++){
            cin>>B[i][j]>>S[i][j];
        }
    }

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j ++){
            if(i==j)dis[i][j] = 0;
            else 
            dis[i][j] = 1e9+1;
        }
    }
    for(int i = 0; i <m; i++){
        int t1,t2,t3;
        cin>>t1>>t2>>t3;
        dis[t1][t2] = t3;
    }
    for(int k = 1; k <= n; k++){
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
            }
        }
    }
    // for(int i = 1; i <= n; i++){
    //     for(int j = 1; j <= n; j ++){cout<<dis[i][j]<<' ';}cout<<'\n';}
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            earn[i][j] = 0;
            for(int l = 0; l < num; l++){
                if(S[j][l]==-1||B[i][l] == -1)continue;
                earn[i][j] = max(earn[i][j], S[j][l] - B[i][l]);
            }
            // cout<<i<<' '<<j<<' '<<earn[i][j]<<" shit\n";
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            dp[i][j] = {earn[i][j],dis[i][j]};
        }
    }
    for(int k = 1; k <= n; k++){
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                // if(i==j)continue;
                if((dp[i][k].ss + dp[k][j].ss) == 0||(dp[i][k].ss + dp[k][j].ss) >= 1e9+1)continue;
                if(dp[i][j].ss == 0 || dp[i][j].ff*(dp[i][k].ss+dp[k][j].ss) < (dp[i][k].ff + dp[k][j].ff)*dp[i][j].ss){
                    dp[i][j] = {(dp[i][k].ff + dp[k][j].ff) , (dp[i][k].ss + dp[k][j].ss)};
                }
            }
        }
    }
    // for(int i = 1; i <= n; i++){
    //     for(int j = 1; j <=n ;j++){
    //         cout<<'('<<earn[i][j]<<','<<dis[i][j]<<") ";
    //     }cout<<'\n';
    // }
    int ans = 0;;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(i!=j)
            ans = max(ans,(dp[i][j].ff + dp[j][i].ff)/(dp[i][j].ss+dp[j][i].ss));
        }
    }
    cout<<ans<<'\n';
}

signed main(){
//    hutao_my_wife    forcalors_so_cute

    int t = 1;
    //cin>>t;
    while(t--){
        solve();
    }
    return 0;
}
/*
5 6 2
100 100 -1 -1 
1000 1000 -1 -1
100 100 -1 -1
1000 1000 -1 -1
1 1 1 1
1 2 1
2 3 1
3 1 1
3 4 1
4 1 1
2 4 1
*/

Compilation message (stderr)

merchant.cpp:9:1: warning: multi-line comment [-Wcomment]
    9 | //  \###################\
      | ^

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