Submission #944682

#	Time	Username	Problem	Language	Result	Execution time	Memory
944682		Darren0724	Travelling Merchant (APIO17_merchant)	C++17	0 / 100	17 ms	3580 KiB

merchant

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#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);
int chmin(int &a,int b){
    if(a>b){
        a=b;return 1;
    }
    return 0;
}
int solve(int t){
    vector dis(2,vector<int>(N,0));
    int flag=0;
    for(int i=0;i<n;i++){
        flag=0;
        for(int j=0;j<m;j++){
            flag|=chmin(dis[0][b[j]],dis[0][a[j]]+c[j]*t);
            flag|=chmin(dis[0][a[j]],dis[0][b[j]]+c[j]*t);
            flag|=chmin(dis[1][b[j]],dis[1][a[j]]+c[j]*t);
            flag|=chmin(dis[1][a[j]],dis[1][b[j]]+c[j]*t);
            if(v[a[j]][0]!=-1){
                flag|=chmin(dis[0][a[j]],dis[1][a[j]]-v[a[j]][1]);
                flag|=chmin(dis[1][a[j]],dis[0][a[j]]+v[a[j]][0]);
            }
            if(v[b[j]][0]!=-1){
                flag|=chmin(dis[0][b[j]],dis[1][b[j]]-v[b[j]][1]);
                flag|=chmin(dis[1][b[j]],dis[0][b[j]]+v[b[j]][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];
    }
    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
• Subtask 2: 0 / 21
• Subtask 3: 0 / 33
• Subtask 4: 0 / 34