Submission #1116477

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116477		whale_island1	Travelling Merchant (APIO17_merchant)	C++14	0 / 100	72 ms	2260 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 = 1e15;
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, ans = 0;
bool vis[105] = {0};
bool check(int x){
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            g[i][j] = min(M,-(earn[i][j] - x*dis[i][j]));
        }
    }
    for(int k = 1; k <= n; k++)
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
        }
    }
    for(int i = 1; i <= n; i++)if(g[i][i] < 0)return 1;
    return 0;
}
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++){
            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]);
            }
        }
    }
    int l = 0, r = 1e9, mid;
    while(r - l > 1){
        mid = (r+l)/2;
        if(check(mid)){
            l = mid;
        }else r = mid;
    }
    cout<<l+1<<'\n';
    //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

4 4 2
100 100 -1 -1 
1000 1000 -1 -1
100 100 -1 -1
1000 1000 -1 -1
1 2 1
2 3 1
3 4 1
4 1 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