Submission #172836

#	Time	Username	Problem	Language	Result	Execution time	Memory
172836		dndhk	Travelling Merchant (APIO17_merchant)	C++14	100 / 100	479 ms	4344 KiB

merchant

#include <bits/stdc++.h>

#define all(v) (v).begin(), (v).end()
#define sortv(v) sort(all(v))
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define pb push_back
#define FI first
#define SE second
#define lb lower_bound
#define ub upper_bound
#define mp make_pair
#define test 0
#define TEST if(test)

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

const int MOD = 1000000007; // 998244353
const int INF = 2e9;
const ll INFLL = 1e16;
const int MAX_N = 100;
const int MAX_K = 1000;

int N, M, K;
ll B[MAX_N+1][MAX_K+1], S[MAX_N+1][MAX_K+1];
ll dist[MAX_N+1][MAX_N+1];

struct Edge{
	int x, y;
	ll c;
};
vector<Edge> edge;

bool chk(ll x){
	for(int i=1; i<=N; i++){
		for(int j=1; j<=N; j++)	dist[i][j] = INFLL;
	}
	for(Edge e : edge){
		dist[e.x][e.y] = min(dist[e.x][e.y], x * e.c);
	}
	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]);
			}
		}
	}
	TEST{
		cout<<x<<endl;
		for(int i=1; i<=N; i++){
			for(int j=1; j<=N; j++){
				cout<<i<<" "<<j<<" "<<dist[i][j]<<endl;
			}
		}cout<<endl;
	}
	for(int i=1; i<=N; i++){
		for(int j=1; j<=N; j++){
			ll r = dist[i][j];
			for(int k=1; k<=K; k++){
				if(B[i][k]!=-1 && S[j][k]!=-1){
					r = min(r, dist[i][j] + B[i][k] - S[j][k]);
				}
			}
			dist[i][j] = r;
		}
	}
	TEST{
		for(int i=1; i<=N; i++){
			for(int j=1; j<=N; j++){
				cout<<i<<" "<<j<<" "<<dist[i][j]<<endl;
			}
		}cout<<endl;
	}
	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]);
			}
		}
	}
	for(int i=1; i<=N; i++){
		if(dist[i][i]<=0)	return true;
	}
	return false;
}

int main(){
	scanf("%d%d%d", &N, &M, &K);
	for(int i=1; i<=N; i++){
		for(int j=1; j<=K; j++){
			scanf("%lld%lld", &B[i][j], &S[i][j]);
		}
	}
	for(int i=1; i<=M; i++){
		int a, b; ll t;
		scanf("%d%d%lld", &a, &b, &t);
		edge.pb({a, b, t});
	}
	ll s = 0, e = 1000000000LL, m;
	while(s<e){
		m = (s+e)/2+1;
		if(chk(m)){
			s = m;
		}else{
			e = m-1;
		}
	}
	cout<<s;
	return 0;
}

Compilation message (stderr)

merchant.cpp: In function 'int main()':
merchant.cpp:92:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &N, &M, &K);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:95:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%lld%lld", &B[i][j], &S[i][j]);
    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:100:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%lld", &a, &b, &t);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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