제출 #953193

#제출 시각아이디문제언어결과실행 시간메모리
953193Itamar여행하는 상인 (APIO17_merchant)C++14
100 / 100
162 ms4296 KiB
#include <iostream> using namespace std; #include <vector> #define vi vector<int> #define ll long long #include <algorithm> #include <set> #include <string> #include <bitset> #include <cmath> #include <math.h> #define pll pair<ll,ll> #define vll vector<ll> #define pi pair<int,int> #include <map> #include <queue> #define x first #define y second #define pd pair<double,double> const int siz = 101; const int MK = 1001; ll dis[siz][siz]; ll pro[siz][siz]; ll pr[siz][2*MK]; int main() { int n, m, K; cin >> n >> m >> K; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (i != j)dis[i][j] = 1e9; } } for (int i = 0; i < n; i++) { for (int j = 0; j < 2 * K; j++) { cin >> pr[i][j]; if (pr[i][j] == -1) { if (j % 2)pr[i][j] = -1e18; else pr[i][j] = 1e18; } } } for (int i = 0; i < m; i++) { ll a, b, c; cin >> a >> b >> c; a--, b--; dis[a][b] = min(dis[a][b],c); } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { for (int k = 0; k < n; k++) { dis[j][k] = min(dis[j][k], dis[j][i] + dis[i][k]); } } } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { for (int k = 0; k < 2*K; k+=2) { pro[i][j] = max(pro[i][j], -pr[i][k] + pr[j][k + 1]); } } } int l = 0, r=1e9; while (l < r) { int mid = (l + r+1) / 2; // is it possible that profit/dis >= mid <--> mid*dis - profit <= 0? vector<vll> procur(n, vll(n,1e18)); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { for (int k = 0; k < n; k++) { procur[i][j] = min(procur[i][j], mid * (dis[i][k] + dis[k][j]) - pro[k][j]); } } } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if(i!=j)procur[i][j] = 200 * procur[i][j] - 1; } } vll dp(n,1e18); dp[0] = 0; bool f = 0; for (int it = 0; it <= n; it++) { vll dpt= dp; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (it == n && dpt[i] > dp[j] + procur[j][i])f = 1; dpt[i] = min(dpt[i], dp[j] + procur[j][i]); } } dp = dpt; } if (f == 1) { l = mid; } else { r = mid-1; } } cout << l; } // Run program: Ctrl + F5 or Debug > Start Without Debugging menu // Debug program: F5 or Debug > Start Debugging menu // Tips for Getting Started: // 1. Use the Solution Explorer window to add/manage files // 2. Use the Team Explorer window to connect to source control // 3. Use the Output window to see build output and other messages // 4. Use the Error List window to view errors // 5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project // 6. In the future, to open this project again, go to File > Open > Project and select the .sln file
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...