Submission #743393

#	Time	Username	Problem	Language	Result	Execution time	Memory
743393		vjudge1	Travelling Merchant (APIO17_merchant)	C++17	0 / 100	54 ms	5756 KiB

merchant

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define ent "\n"

const int maxn = 1e6 + 100;
const ll INF = (ll)1e18;
const int MOD = 1e9 + 7;
const int inf = (1<<30);
const int maxl = 20;
const int P = 31;

int n, m, k;
ll b[110][1010];
ll s[110][1010];
ll d[110][110];
ll c[110][110];
ll a[110][110];
vector<pii> g[110];

void calc(int s){
    fill(d[s] + 1, d[s] + n + 1, INF);
    d[s][s] = 0;
    set<pll> st;
    st.insert({0, s});
    while(st.size()){
        int v = st.begin()->second;
        st.erase(st.begin());
        for(auto [to, w]: g[v]){
            if(d[s][to] > d[s][v] + w){
                st.erase({d[s][to], to});
                d[s][to] = d[s][v] + w;
                st.insert({d[s][to], to});
            }
        }
    }
}

bool ok(ll x){
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(i == j) a[i][j] = -INF;
            else a[i][j] = c[i][j] - d[i][j] * min(INF / d[i][j], x);
        }
    }
    for(int k = 1; k <= n; k++){
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                a[i][j] = max(a[i][j], a[i][k] + a[k][j]);
            }
        }
    }
    for(int i = 1; i <= n; i++){
        if(a[i][i] >= 0) return 1;
    }
    return 0;
}

void test(){
    cin >> n >> m >> k;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= k; j++){
            cin >> b[i][j] >> s[i][j];
        }
    }
    for(int i = 1; i <= m; i++){
        int a, b, c;
        cin >> a >> b >> c;
        g[a].push_back({b, c});
    }
    for(int i = 1; i <= n; i++){
        calc(i);
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            for(int t = 1; t <= k; t++){
                if(b[i][t] != -1 && s[j][t] != -1) c[i][j] = max(c[i][j], s[j][t] - b[i][t]);
            }
        }
    }
    ll ans = 0;
    for(int l = 1, r = 1e9; l <= r;){
        int mid = (l + r) >> 1;
        if(!ok(mid)) r = mid - 1;
        else l = mid + 1, ans = mid;
    }
    cout << ans;
}
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int t; t = 1;
    while(t--) test();
}

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