제출 #1021074

#제출 시각아이디문제언어결과실행 시간메모리
1021074JuliaTatad여행하는 상인 (APIO17_merchant)C++17
100 / 100
99 ms3684 KiB
#include <iostream> #include <vector> #include <algorithm> using namespace std; int n, m, k; long long int INF = 2 * 1e18; vector<vector<pair<int, int>>> markets; vector<vector<int>> gr; vector<vector<int>> profits; vector<bool> used; long long int MIN(long long int a, long long int b) { if (a < b) { return a; } return b; } struct Edge { int from, to, w; Edge(int from, int to, int w) : from(from), to(to), w(w) {} }; void dfs(int v) { used[v] = true; for (auto u : gr[v]) { if (!used[u]) { dfs(u); } } } int main() { cin >> n >> m >> k; markets.resize(n, vector<pair<int, int>>(k)); vector<vector<long long int>> d(n, vector<long long int>(n, INF)); for (int i = 0; i < n; i++) { for (int j = 0; j < k; j++) { cin >> markets[i][j].first; cin >> markets[i][j].second; } } gr.resize(n); vector<Edge> edges; for (int i = 0; i < m; i++) { int v, u, t; cin >> v >> u >> t; v--; u--; gr[v].push_back(u); edges.push_back(Edge(v, u, t)); } profits.assign(n, vector<int>(n, 0)); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { for (int x = 0; x < k; x++) { if (markets[i][x].first != -1 && markets[j][x].second != -1) { profits[i][j] = max(profits[i][j], -markets[i][x].first + markets[j][x].second); } } } } /* for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cout << "profits[" << i << "][" << j << "] = " << profits[i][j] << endl; } } */ vector<vector<double>> len(n, vector<double>(n, INF)); /* for (int i = 0; i < n; i++) { len[i][i] = 0; } */ for (auto& e : edges) { len[e.from][e.to] = MIN(len[e.from][e.to], e.w); } for (int x = 0; x < n; x++) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (len[i][x] < INF && len[x][j] < INF) { len[i][j] = MIN(len[i][j], len[i][x] + len[x][j]); } } } } /* d.assign(n, vector<long long int>(n, INF)); long long int m = 0; for (int i = 0; i < n; i++) { d[i][i] = 0; } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (len[i][j] < INF) { d[i][j] = m * len[i][j] - profits[i][j]; } } } for (int x = 0; x < n; x++) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (d[i][x] < INF && d[x][j] < INF) { d[i][j] = MIN(d[i][j], d[i][x] + d[x][j]); } } } } int cycles = 0; for (int i = 0; i < n; i++) { if (d[i][i] < 0) { cycles = 1; } } if (cycles == 0) { cout << 0 << "\n"; return 0; } */ long long int l = 0; long long int h = 2 * 1e9; while (l + 1 < h) { long long int m = (l + h) / 2; //double m = mid - 0.0001; d.clear(); d.assign(n, vector<long long int>(n, INF)); /* for (int i = 0; i < n; i++) { d[i][i] = 0; } */ for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (len[i][j] < INF) { d[i][j] = m * len[i][j] - profits[i][j]; } } } for (int x = 0; x < n; x++) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (d[i][x] < INF && d[x][j] < INF) { d[i][j] = MIN(d[i][j], d[i][x] + d[x][j]); } } } } int cycles = 0; for (int i = 0; i < n; i++) { if (d[i][i] <= 0) { cycles = 1; } } if (cycles == 1) { l = m; } else { h = m; } } cout << l << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...