Submission #1117016

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117016		Sofiatpc	Travelling Merchant (APIO17_merchant)	C++14	12 / 100	12 ms	1276 KiB

merchant

#include <bits/stdc++.h>

using namespace std;

#define sz(v) (int)v.size()
#define fi first
#define sc second
const int MAXN = 105, MAXK = 1005, INF = 1e9+5;
int b[MAXN][MAXK], s[MAXN][MAXK];
vector< pair<int,int>> adj[2][MAXN];
int dist[2][MAXN], n;

void dij(int z){
    for(int i = 1; i <= n; i++)dist[z][i] = INF;

    set< pair<int,int> > st;
    dist[z][1] = 0;
    st.insert({0,1});

    while(!st.empty()){
        int x = st.begin()->sc; st.erase(st.begin());

        for(int i = 0; i < sz(adj[z][x]); i++){
            int viz = adj[z][x][i].fi, w = adj[z][x][i].sc;
            if(dist[z][viz] > dist[z][x] + w){
                st.erase({dist[z][viz],viz});
                dist[z][viz] = dist[z][x] + w;
                st.insert({dist[z][viz],viz});
            }
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cin.tie(0);

    int m,k; 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;
        adj[0][a].emplace_back(b,c);
        adj[1][b].emplace_back(a,c);
    }

    dij(0);
    dij(1);

    int l = 0;
    for(int i = 1; i <= n; i++){
        int x = 0;
        for(int j = 1; j <= k; j++) x = max(x, s[i][j]-b[1][j]);
        if(dist[0][i]+dist[1][i] == 0)continue;
        int y = x/(dist[0][i]+dist[1][i]);
        l = max(l, y );
    }
    cout<<l<<"\n";
}

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