Submission #643001

#	Time	Username	Problem	Language	Result	Execution time	Memory
643001		christinelynn	Travelling Merchant (APIO17_merchant)	C++17	12 / 100	21 ms	2380 KiB

merchant

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;
const ll mod=1e9+7;
const ll maxn=1e6+5;
const int INF=1e9+5;
#define ok ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define fi first
#define se second
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define endl '\n'
int n, m, k, u, v, w, dis[105][105], ans;
pii item[105][1005];
vector<pii> adj[105];
bool bs=1;
int main() {
    ok
    cin >> n >> m >> k;
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=k; j++) cin >> item[i][j].fi >> item[i][j].se;
    }
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) dis[i][j]=INF;
        dis[i][i]=0;
    }
    for(int i=0; i<m; i++) {
        cin >> u >> v >> w;
        adj[u].pb({v, w});
        dis[u][v]=min(dis[u][v], w);
    }
    if(n==1) {
        cout << 0;
        return 0;
    }
    for(int i=2; i<=n; i++) {
        for(int j=1; j<=k; j++) {
            if(item[i][j].fi!=-1) bs=0;
        }
    }
    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]);
            }
        }
    }
    if(bs) {
        for(int i=2; i<=n; i++) {
            if(dis[1][i]!=INF && dis[i][1]!=INF) {
                for(int j=1; j<=k; j++) {
                    if(item[1][j].fi>0 && item[i][j].se>0) {
                        ans=max(ans, (item[i][j].se-item[1][j].fi)/(dis[1][i]+dis[i][1]));
                    }
                }
            }
        }
        cout << ans;
    }
}

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