제출 #881510

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
881510		ttamx	Travelling Merchant (APIO17_merchant)	C++14	0 / 100	829 ms	3956 KiB

merchant

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N=105;
const int M=205;
const int K=1005;
const ll inf=1e18;

int n,k,m;
ll b[N][K],s[N][K];
ll dist[N][N],dp[N][N];

bool check(ll cost){
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)dp[i][j]=inf;
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(i!=j)
        for(int k=1;k<=::k;k++)if(b[i][k]>0&&s[j][k]>0)
            dp[i][j]=min(dp[i][j],dist[i][j]*cost+min(0ll,b[i][k]-s[j][k]));
    for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
    for(int i=1;i<=n;i++)if(dp[i][i]<=0)return true;
    return false;
}

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    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<=n;i++)for(int j=1;j<=n;j++)dist[i][j]=i==j?0:inf;
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin >> u >> v >> w;
        dist[u][v]=w;
    }
    for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
    ll l=0,r=1e9;
    while(l<r){
        ll m=(l+r+1)/2;
        if(check(m))l=m;
        else r=m-1;
    }
    cout << l << "\n";
}

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