oj.uz

답안 #944831

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
944831 2024-03-13T06:17:55 Z Darren0724 여행하는 상인 (APIO17_merchant) C++17
0 / 100
 48 ms 1368 KB 
#include<bits/stdc++.h>
using namespace std;
#define all(x) x.begin(),x.end()
#define abcorz ios_base::sync_with_stdio(false);cin.tie(0);
const int N=105;
const int M=10005;
const int INF=1.05e9;
const int mod=1e9+7;
int n,m,k;
vector<int> v[N];
vector<int> a(M),b(M),c(M);
vector dis(N,vector(N,INF));
vector adj(N,vector<int>(N,0));
inline void chmin(int &a,int b){
    a=(a>b?b:a);
}
void run(){
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                chmin(dis[i][j],dis[i][k]+dis[k][j]);
            }
        }
    }
}
int solve(int t){
    vector<vector<int>> dis1(n+1,vector<int>(n+1,INF));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i==j||dis[i][j]==INF)continue;
            dis1[i][j]=dis[i][j]*t-adj[i][j];
        }
    }
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                chmin(dis1[i][j],dis1[i][k]+dis1[k][j]);
            }
        }
    }
    int flag=0;
    for(int i=1;i<=n;i++){
        flag|=(dis1[i][i]<=0);
    }
    return flag;
}
int32_t main(){
    abcorz;
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++){
        for(int j=0;j<k*2;j++){
            int p;cin>>p;
            v[i].push_back(p);
        }
    }
    for(int i=0;i<m;i++){
        cin>>a[i]>>b[i]>>c[i];
        dis[a[i]][b[i]]=c[i];
    }
    run();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            int mx=0;
            for(int k1=0;k1<k;k1++){
                if(v[j][k1*2+1]!=-1&&v[i][k1*2]!=-1){
                    mx=max(mx,v[j][k1*2+1]-v[i][k1*2]);
                }
            }
            adj[i][j]=mx;
        }
    }
    int l=0,r=INF;
    while(r-l>1){
        int mid=(l+r)>>1;
        if(solve(mid))l=mid;
        else r=mid;
    }
    cout<<l<<endl;
    return 0;
}

Subtask #1
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 48 ms 1368 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 31 ms 600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -