Submission #409141

#	Time	Username	Problem	Language	Result	Execution time	Memory
409141		myrcella	Travelling Merchant (APIO17_merchant)	C++17	100 / 100	117 ms	2244 KiB

merchant

//by szh
#include<bits/stdc++.h>
using namespace std;
 
#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a;i<(b);i++)
#define MP make_pairta'fang'
#define SZ(x) (int(x.size()))
#define ll long long
#define mod 1000000007
#define ALL(x) x.begin(),x.end()
void inc(int &a,int b) {a=(a+b)%mod;}
void dec(int &a,int b) {a=(a-b+mod)%mod;}
int lowbit(int x) {return x&(-x);}
ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;}
 
const int maxn=111;
 
int N,M,K;
int S[maxn][maxn*maxn],B[maxn][maxn*maxn];
 
int	dis[maxn][maxn];
int dp[maxn][maxn];
ll d[maxn][maxn],mp[maxn][maxn];
 
bool check(int val) {
	rep(i,0,N)
		rep(j,0,N) {
      		if (i==j) mp[i][j]=d[i][j]=0;
			else if (dis[i][j]<mod) mp[i][j]=d[i][j]=1ll*dis[i][j]*val-dp[i][j];
      		else mp[i][j]=d[i][j]=1e12;
		}
	ll len=1;
	rep(k,0,N) {
		rep(i,0,k)
			rep(j,0,k) len=min(len,d[i][j]+mp[j][k]+mp[k][i]);
		rep(i,0,N)
			rep(j,0,N) d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
	}
	return len<=0;
}
 
int main() {
//	freopen("input.txt","r",stdin);	
	std::ios::sync_with_stdio(false);cin.tie();
	cin>>N>>M>>K;
	memset(dis,0x3f,sizeof(dis));
	rep(i,0,N) {
		rep(j,0,K) cin>>B[i][j]>>S[i][j];
	}
	rep(i,0,M) {
		int u,v,w;
		cin>>u>>v>>w;
		u--,v--;
		dis[u][v]=min(dis[u][v],w);
	}
	rep(k,0,N)
		rep(i,0,N)
			rep(j,0,N) dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
	rep(i,0,N)
		rep(j,0,N) {
			dp[i][j]=0;
			rep(k,0,K) {
				if (B[i][k]==-1||S[j][k]==-1) continue;
				dp[i][j]=max(dp[i][j],-B[i][k]+S[j][k]);
//				cout<<i<<" "<<j<<" "<<k<<" "<<dp[i][j]<<endl;
			}
		}
	int l=0,r=1e9;
	while (l<r) {
		int mid=l+r+1>>1;
		if (check(mid)) l=mid;
		else r=mid-1;
	}
	cout<<l;
	return 0;
}

Compilation message (stderr)

merchant.cpp: In function 'int main()':
merchant.cpp:78:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   78 |   int mid=l+r+1>>1;
      |           ~~~^~

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