oj.uz

답안 #947400

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
947400 2024-03-16T06:15:57 Z parsadox2 여행하는 상인 (APIO17_merchant) C++14
0 / 100
 52 ms 4176 KB 
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define debug(x) cout << #x << " = " << x << " ";
#define fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define S second
#define F first
#define int long long
using namespace std;
 
const int maxn = 1e2 + 10 , maxk = 1e3 + 10 , ili = 1e9 + 10;
const int inf = 1e18 + 10;
int n , m , k , s[maxn][maxk] , b[maxn][maxk] , c[maxn][maxn];
ll dis[maxn][maxn] , ans[maxn][maxn];
vector <pair<ll, int>> g[maxn];
 
void allinf(ll tmp[][maxn])
{
	for(int i = 0 ; i < maxn ; i++)
		for(int j = 0 ; j < maxn ; j++)
			tmp[i][j] = inf;
}
 
void floyd(ll dist[][maxn])
{
	for(int i = 0 ; i < n ; i++)
		for(auto u : g[i])
			dist[i][u.S] = min(dist[i][u.S] , u.F);
	for(int kk = 0 ; kk < n ; kk++)
		for(int i = 0 ; i < n ; i++)
			for(int j = 0 ; j < n ; j++)
				dist[i][j] = min(dist[i][j] , dist[i][kk] + dist[kk][j]);
}
 
int C(int v , int u)
{
	int res = 0;
	for(int i = 0 ; i < k ; i++)
		if(b[v][i] != -1 && s[u][i] != -1)
			res = max(res , s[u][i] - b[v][i]);
	return res;
}
 
int32_t main()
{
	fast;
	
	cin >> n >> m >> k;
	for(int i = 0 ; i < n ; i++)
		for(int j = 0 ; j < k ; j++)
			cin >> b[i][j] >> s[i][j];
	for(int i = 0 ; i < m ; i++)
	{
		int v , u , w;
		cin >> v >> u >> w;
		v--; u--;
		g[v].pb({w , u});
	}
	allinf(dis);
	floyd(dis);
	ll low = 0 , high = ili;
	for(int i = 0 ; i < n ; i++)
		for(int j = 0 ; j < n ; j++)
			if(i != j)
				c[i][j] = C(i , j);
	while(high - low > 1)
	{
		ll mid = (high + low) / 2;
		for(int i = 0 ; i < n ; i++)	g[i].clear();
		for(int i = 0 ; i < n ; i++)
			for(int j = 0 ; j < n ; j++)
				if(i != j)
					g[i].pb({(inf / dis[i][j] < mid ? inf : 1LL * mid * dis[i][j] - c[i][j]) , j});
		allinf(ans);
		floyd(ans);
		ll mn = 667;
		for(int i = 0 ; i < n ; i++) mn = min(mn , ans[i][i]);
		if(mn < 0)
			low = mid;
		else
			high = mid;
	}
	cout << low << endl;
	return 0;
}

Subtask #1
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 47 ms 3672 KB Output is correct
2 Correct 30 ms 1628 KB Output is correct
3 Correct 39 ms 1628 KB Output is correct
4 Correct 6 ms 1112 KB Output is correct
5 Correct 6 ms 1112 KB Output is correct
6 Correct 5 ms 1116 KB Output is correct
7 Correct 6 ms 1220 KB Output is correct
8 Incorrect 1 ms 604 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 1116 KB Output is correct
2 Correct 6 ms 1220 KB Output is correct
3 Incorrect 1 ms 604 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 1884 KB Output is correct
2 Correct 52 ms 4176 KB Output is correct
3 Correct 31 ms 1880 KB Output is correct
4 Correct 32 ms 1884 KB Output is correct
5 Incorrect 33 ms 1884 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 1884 KB Output is correct
2 Correct 52 ms 4176 KB Output is correct
3 Correct 31 ms 1880 KB Output is correct
4 Correct 32 ms 1884 KB Output is correct
5 Incorrect 33 ms 1884 KB Output isn't correct
6 Halted 0 ms 0 KB -