제출 #512192

#제출 시각아이디문제언어결과실행 시간메모리
512192InternetPerson10여행하는 상인 (APIO17_merchant)C++17
12 / 100
69 ms3140 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; vector<vector<ll>> b, s; vector<vector<pair<int, int>>> adj; ll dist[100][100], gain[100][100]; const ll BIG = 1234567890; int main() { int n, m, k; cin >> n >> m >> k; b.resize(n); s.resize(n); adj.resize(n); for(int i = 0; i < n; i++) { b[i].resize(k); s[i].resize(k); for(int j = 0; j < k; j++) { cin >> b[i][j] >> s[i][j]; } for(int j = 0; j < n; j++) { dist[i][j] = BIG; gain[i][j] = 0; } } for(int i = 0; i < m; i++) { int x, y, t; cin >> x >> y >> t; x--; y--; adj[x].push_back({y, t}); dist[x][y] = t; } // floyd-warshall for(int z = 0; z < n; z++) { for(int x = 0; x < n; x++) { for(int y = 0; y < n; y++) { dist[x][y] = min(dist[x][y], dist[x][z] + dist[z][y]); } } } // gain calculation for(int x = 0; x < n; x++) { for(int y = 0; y < n; y++) { for(int i = 0; i < k; i++) { if(b[x][i] == -1 || s[y][i] == -1) continue; gain[x][y] = max(gain[x][y], s[y][i] - b[x][i]); } } } // Subtask 1 ll ans = 0; for(int i = 1; i < n; i++) { ans = max(ans, (gain[0][i] + gain[i][0])/(dist[0][i] + dist[i][0])); } cout << ans << '\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...