Submission #643210

#TimeUsernameProblemLanguageResultExecution timeMemory
643210Sara_smdTravelling Merchant (APIO17_merchant)C++14
0 / 100
66 ms1492 KiB
//Khoda Hast :)// #include<bits/stdc++.h> #define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) #define ret(x) return cout << x << endl, 0; #define all(x) x.begin(),x.end() #define pf push_front #define ff pop_front #define pb push_back #define bb pop_back #define F first #define S second using namespace std; const int N = 200, M = 1e4, T = 1e3 + 10, OO = 1e9; int a[N][T], b[N][T], l[N][N], p[N][N], n, m, t; long long d[N][N]; vector<int> adj[N]; bool check(int x) { bool is = false; for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) d[i][j] = 1ll * l[i][j] * x - 1ll * p[i][j]; for(int k = 0; k < n; k++) for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) { if(i == j && i != k && d[i][k] + d[k][j] <= 0) is = true; d[i][j] = min(d[i][j], d[i][k] + d[k][j]); } return is; } int main() { ios; cin >> n >> m >> t; for(int i = 0; i < n; i++) for(int j = 0; j < t; j++) cin >> a[i][j] >> b[i][j]; for(int i = 0; i < m; i++) { int u, v, w; cin >> u >> v >> w; u--, v--; adj[u].pb(v); adj[v].pb(u); d[u][v] = w; d[v][u] = w; } for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) if(i != j && !d[i][j]) d[i][j] = 1ll * OO; for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) p[i][j] = -OO; for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) l[i][j] = OO; for(int i = 0; i < n; i++) { l[i][i] = 0; for(auto j : adj[i]) l[i][j] = d[i][j]; } for(int k = 0; k < n; k++) for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) l[i][j] = min(l[i][j], l[i][k] + l[k][j]); for(int i = 0; i < n; i++) adj[i].clear(); for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) { bool is = false; for(int k = 0; k < t; k++) if(a[i][k] != -1 && b[j][k] != -1) p[i][j] = max(p[i][j], b[j][k] - a[i][k]), is = true; if(is) adj[i].pb(j); } int lft = 0, rgt = OO; while(lft + 1 < rgt) { int mid = (lft + rgt) / 2; if(check(mid)) lft = mid; else rgt = mid; } cout << lft << endl; 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...