Submission #903906

#	Time	Username	Problem	Language	Result	Execution time	Memory
903906		irmuun	Travelling Merchant (APIO17_merchant)	C++17	12 / 100	28 ms	1880 KiB

merchant

#include<bits/stdc++.h>
 
using namespace std;
 
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll n,m,k;
    cin>>n>>m>>k;
    ll b[n][k],s[n][k];
    for(ll i=0;i<n;i++){
        for(ll j=0;j<k;j++){
            cin>>b[i][j]>>s[i][j];
        }
    }
    vector<pair<ll,ll>>adj[n];
    for(ll i=0;i<m;i++){
        ll u,v,t;
        cin>>u>>v>>t;
        u--,v--;
        adj[u].pb({v,t});
    }
    ll dist[n][n];
    for(ll i=0;i<n;i++){
        for(ll j=0;j<n;j++){
            dist[i][j]=1e18;
        }
    }
    for(ll i=0;i<n;i++){
        set<pair<ll,ll>>st;
        st.insert({0,i});
        dist[i][i]=0;
        while(!st.empty()){
            auto [t,x]=*st.begin();
            st.erase(st.begin());
            for(auto [j,d]:adj[x]){
                if(t+d<dist[i][j]){
                    if(dist[i][j]<1e18){
                        st.erase({dist[i][j],j});
                    }
                    dist[i][j]=t+d;
                    st.insert({dist[i][j],j});
                }
            }
        }
    }
    ll ans=0;
    for(ll i=0;i<n;i++){
        for(ll j=0;j<n;j++){//i -> 0 -> i
            if(i==j) continue;
            if(dist[i][j]==1e18||dist[j][i]==1e18){
                continue;
            }
            ll mx=0;
            for(ll r=0;r<k;r++){
                if(b[i][r]>-1&&s[j][r]>-1){
                    mx=max(mx,s[j][r]-b[i][r]);
                }
            }
            ans=max(ans,mx/(dist[i][j]+dist[j][i]));
        }
    }
    cout<<ans;
}

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