제출 #1189042

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1189042		Malix	Travelling Merchant (APIO17_merchant)	C++20	100 / 100	99 ms	2212 KiB

merchant

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
typedef tuple<ll,ll,ll> ti;
typedef vector<ll> li;
typedef vector<li> lii;
 
#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define LSOne(s) ((s)&(-s))
 
ll INF=1000000000000000010;
int inf=1e9+10;
ll M=1e9+7;

int n,m,k;
ll X[100][1000],Y[100][1000],dist[100][100],p[100][100],a[100][100];

int main() {   
// ios::sync_with_stdio(0);
// cin.tie(0);
    cin>>n>>m>>k;
    REP(i,0,n)REP(j,0,k)cin>>X[i][j]>>Y[i][j];
    REP(i,0,100)REP(j,0,100)dist[i][j]=INF;
    REP(i,0,m){
        int x,y;cin>>x>>y;
        ll z;cin>>z;
        x--;y--;
        dist[x][y]=z;
    }
    REP(i,0,n)dist[i][i]=0;
    REP(x,0,n)REP(i,0,n)REP(j,0,n)if(dist[i][x]!=INF&&dist[x][j]!=INF)dist[i][j]=min(dist[i][j],dist[i][x]+dist[x][j]);
    REP(i,0,n)REP(j,0,n){
        if(i==j)continue;
        p[i][j]=0;
        if(dist[i][j]!=INF)REP(x,0,k)if(Y[j][x]!=-1&&X[i][x]!=-1)p[i][j]=max(p[i][j],Y[j][x]-X[i][x]);
    }
    ll l=0,r=1e9;
    while(l!=r){
        ll mid=(l+r+1)/2;
        bool flag=0;
        REP(i,0,n)REP(j,0,n){
            if(i==j)a[i][j]=INF;
            else if(dist[i][j]==INF)a[i][j]=INF;
            else a[i][j]=dist[i][j]*mid-p[i][j];
        }
        REP(x,0,n)REP(i,0,n)REP(j,0,n)if(a[i][x]!=INF&&a[x][j]!=INF)a[i][j]=min(a[i][j],a[i][x]+a[x][j]);
        REP(i,0,n)if(a[i][i]<=0)flag=1;
        if(flag)l=mid;
        else r=mid-1;
    }
    cout<<l;
}

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