제출 #942583

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
942583		vania_javai	여행하는 상인 (APIO17_merchant)	C++14	0 / 100	882 ms	5976 KiB

merchant

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 110;
const int Maxn = 1000;
const ll inf = 1e15;
const long double M = 1e11;
const int sq = 450;
#define debug(x)  cerr << "(" << (#x) << "): " << (x) << endl
#define lc (id << 1)
#define rc (lc | 1)
#define all(x) x.begin(), x.end()
#define SZ(x) x.size()

vector<pii> edg[N];
long double dis[N], dp[N][N][2], bs[N][N], a[N][Maxn][2];
int n, q;
bool mark[N];
void min_dis(){
	///// Base:
	for(int i = 0; i < n; i++)	
		for(int j = 0; j < n; j++)
			dp[i][j][0] = dp[i][j][1] = (i != j) * inf;
			
	for(int v = 0; v < n; v++)
		for(pii p: edg[v])
			dp[v][p.first][0] = p.second; 

	////// Update: 
	for(int k = 0; k < n; k++)
		for(int i = 0; i < n; i++)
			for(int j = 0; j < n; j++)
				dp[i][j][1 - k & 1] = min(dp[i][j][k & 1], dp[i][k][k & 1] + dp[k][j][k & 1]);
}

void best_sell(){
	for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j++)
			for(int k = 0; k < q; k++)
				if(a[i][k][0] > 0 && a[j][k][1] > 0)
					bs[i][j] = max(bs[i][j], -a[i][k][0] + a[j][k][1]);
}

bool check(long double x){
	// c / l > x;   c > x * l   x * l - c < 0;
	for(pii p: edg[0])	mark[p.first] = 1;
	for(int i = 0; i < n; i++)	if(!mark[i])	edg[0].push_back({i, inf});
	
	for(int i = 1; i < n; i++)	dis[i] = M;
	for(int i = 1; i < n; i++)
		for(int v = 0; v < n; v++)
			for(int u = 0; u < n; u++)
				if(dp[u][v][n & 1] <= inf)
					dis[v] = min(dis[v], dis[u] + x * dp[u][v][n & 1] - bs[u][v]);
			
	
	for(int v = 0; v < n; v++)
		for(int u = 0; u < n; u++)
			if(dp[v][u][n & 1] <= inf){
			long double mn = dis[v] + x * dp[v][u][n & 1] - bs[v][u];
			if(mn < dis[u])	return 1;
		}
	return 0;
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	int m;	cin>> n>> m>> q;
	for(int i = 0; i < n; i++)
		for(int j = 0; j < q; j++)	cin>> a[i][j][0] >> a[i][j][1];
	
	for(int i = 0; i < m; i++){
		int x, y, w;	cin>> x>> y>> w;
		edg[x - 1].push_back({y - 1, w});
	}
	
	min_dis();
	best_sell();

	long double l = -1, r = M + 1.0;
	for(int i = 0; i < 100; i++){
		long double mid = (l + r) / 2.0;
		(check(mid)? l: r) = mid;
	}
	cout<< (ll)r;
	return 0;
} 

컴파일 시 표준 에러 (stderr) 메시지

merchant.cpp: In function 'void min_dis()':
merchant.cpp:34:16: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   34 |     dp[i][j][1 - k & 1] = min(dp[i][j][k & 1], dp[i][k][k & 1] + dp[k][j][k & 1]);
      |              ~~^~~

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