제출 #591720

#제출 시각아이디문제언어결과실행 시간메모리
591720piOOE여행하는 상인 (APIO17_merchant)C++17
100 / 100
113 ms3276 KiB
//#define _GLIBCXX_DEBUG //#pragma GCC optimize("Ofast") //#pragma GCC optimize("unroll-loops") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #include <bits/stdc++.h> using namespace std; //#include <ext/pb_ds/assoc_container.hpp> // //using namespace __gnu_pbds; // //template<typename T> //using ordered_set = tree<T, null_type, less < T>, rb_tree_tag, tree_order_statistics_node_update>; template<typename T> using normal_queue = priority_queue<T, vector<T>, greater<>>; mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count()); #define trace(x) cout << #x << ": " << (x) << endl; #define all(x) begin(x), end(x) #define rall(x) rbegin(x), rend(x) #define uniq(x) x.resize(unique(all(x)) - begin(x)) #define ld long double #define sz(s) ((int) size(s)) #define pii pair<int, int> #define mp(x, y) make_pair(x, y) #define int128 __int128 #define pb push_back #define eb emplace_back #define fi first #define se second #define itn int typedef long long ll; template<typename T> bool ckmn(T &x, T y) { if (x > y) { x = y; return true; } return false; } template<typename T> bool ckmx(T &x, T y) { if (x < y) { x = y; return true; } return false; } int bit(int x, int b) { return (x >> b) & 1; } int rand(int l, int r) { return (int) ((ll) rnd() % (r - l + 1)) + l; } const ll infL = 3e18; const int infI = 1000000000 + 7; const int infM = 2139062143; const ll infML = 9187201950435737471LL; const int maxN = 101, maxK = 1001; const ll mod = 998244353; const ld eps = 1e-9; int N, M, K, b[maxN][maxK], s[maxN][maxK], mx[maxN][maxN]; ll d[maxN][maxN], dist[maxN][maxN]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> N >> M >> K; for (int i = 0; i < N; ++i) { for (int j = 0; j < K; ++j) { cin >> b[i][j] >> s[i][j]; } fill(dist[i], dist[i] + N, infI); dist[i][i] = 0; } for (int i = 0; i < M; ++i) { int a, v, w; cin >> a >> v >> w; --a, --v; dist[a][v] = w; } for (int k = 0; k < N; ++k) for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) if (dist[i][k] < infI && dist[k][j] < infI) ckmn(dist[i][j], dist[i][k] + dist[k][j]); for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { for (int k = 0; k < K; ++k) { if (b[i][k] != -1 && s[j][k] != -1) ckmx(mx[i][j], s[j][k] - b[i][k]); } } } int l = 0, r = infI; while (l + 1 < r) { int mid = (l + r) >> 1; for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { d[i][j] = infL; if (i != j && dist[i][j] < infI) { d[i][j] = dist[i][j] * 1LL * mid - mx[i][j]; } } } for (int k = 0; k < N; ++k) { for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { if (d[i][k] < infL && d[k][j] < infL) ckmn(d[i][j], d[i][k] + d[k][j]); } } } bool ok = false; for (int i = 0; i < N; ++i) { if (d[i][i] <= 0) { ok = true; } } if (ok) l = mid; else r = mid; } cout << l; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...