Submission #232210

#	Time	Username	Problem	Language	Result	Execution time	Memory
232210		BamiTorabi	Travelling Merchant (APIO17_merchant)	C++14	100 / 100	120 ms	4344 KiB

merchant

//Sasayego! Sasayego! Shinzou wo Sasageyo!

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <numeric>
#include <bitset>
#include <ctime>
#define debug(x)  cerr << #x << " = " << x << endl
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <ll, ll> pll;
typedef pair <int, int> pii;

const int maxN = 1e2 + 5;
const int maxK = 1e3 + 5;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;

ll S[maxN][maxK], B[maxN][maxK];
ll G[maxN][maxN], C[maxN][maxN];
int n, k, D[maxN][maxN];

bool isVal(ll X){
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			G[i][j] = X * D[i][j] - C[i][j];
	for (int x = 1; x <= n; x++)
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				if (i != j)
					G[i][j] = min(G[i][j], G[i][x] + G[x][j]);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j < i; j++)
			if (G[i][j] + G[j][i] <= 0)
				return true;
	return false;
}

int main(){
	time_t START = clock();
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	memset(D, 63, sizeof D);
	int m; scanf("%d%d%d", &n, &m, &k);
	for (int i = 1; i <= n; i++)
		for (int j = 0; j < k; j++)
			scanf("%lld%lld", &B[i][j], &S[i][j]);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			for (int x = 0; x < k; x++)
				if (S[j][x] != -1 && B[i][x] != -1)
					C[i][j] = max(C[i][j], S[j][x] - B[i][x]);
	for (int i = 1; i <= n; i++)
		D[i][i] = 0;
	while (m--){
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		D[u][v] = min(D[u][v], w);
	}
	for (int x = 1; x <= n; x++)
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				D[i][j] = min(D[i][x] + D[x][j], D[i][j]);
	int lt = 0, rt = MOD;
	while (rt - lt > 1){
		int md = (lt + rt) >> 1;
		(isVal(md) ? lt : rt) = md;
	}
	printf("%d\n", lt);
	time_t FINISH = clock();
	cerr << "Execution time: " << (ld)(FINISH - START) / CLOCKS_PER_SEC * 1000.0 << " milliseconds.\n";
	return 0;
}
 

Compilation message (stderr)

merchant.cpp: In function 'int main()':
merchant.cpp:54:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int m; scanf("%d%d%d", &n, &m, &k);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:57: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:67:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &u, &v, &w);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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