제출 #1200923

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1200923		PlayVoltz	여행하는 상인 (APIO17_merchant)	C++20	100 / 100	92 ms	2120 KiB

merchant

#include <cstdio>
#include <stdio.h>
#include <stdbool.h>
#include <iostream>
#include <map>
#include <vector>
#include <climits>
#include <stack>
#include <string>
#include <queue>
#include <algorithm>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <cmath>
#include <cctype>
#include <bitset>
#include <iomanip>
#include <cstring>
#include <numeric>
#include <cassert>
using namespace std;

#define int long long
#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second

vector<vector<int> > t, p, graph;
vector<vector<pii> > vect;
 
int32_t main(){
	int n, m, k, a, b, c;
	cin>>n>>m>>k;
	vect.resize(n+1, vector<pii>(k));
	graph.resize(n+1, vector<int>(n+1));
	t.resize(n+1, vector<int>(n+1, LLONG_MAX/2));
	p.resize(n+1, vector<int>(n+1, 0));
	for (int i=1; i<=n; ++i)for (int j=0; j<k; ++j)cin>>vect[i][j].fi>>vect[i][j].se;
	while (m--){
		cin>>a>>b>>c;
		t[a][b]=min(t[a][b], c);
	}
	for (int l=1; l<=n; ++l)for (int i=1; i<=n; ++i)for (int j=1; j<=n; ++j)t[i][j]=min(t[i][j], t[i][l]+t[l][j]);
	for (int i=1; i<=n; ++i)for (int j=1; j<=n; ++j)for (int l=0; l<k; ++l)if (vect[i][l].fi!=-1&&vect[j][l].se!=-1)p[i][j]=max(p[i][j], vect[j][l].se-vect[i][l].fi);
	int low=0, high=1e9;
	while (low+1<high){
		int mid=(low+high)/2;
		for (int i=1; i<=n; ++i)for (int j=1; j<=n; ++j)graph[i][j]=p[i][j]-mid*min((LLONG_MAX/2)/mid, t[i][j]);
		for (int l=1; l<=n; ++l)for (int i=1; i<=n; ++i)for (int j=1; j<=n; ++j)graph[i][j]=max(graph[i][j], graph[i][l]+graph[l][j]);
		bool can=0;
		for (int i=1; i<=n; ++i)if (graph[i][i]>=0)can=1;
		if (can)low=mid;
		else high=mid;
	}
	cout<<low;
}

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