Submission #1040564

#TimeUsernameProblemLanguageResultExecution timeMemory
1040564MuhammetTravelling Merchant (APIO17_merchant)C++17
0 / 100
12 ms12888 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long int #define sz(x) (int)x.size() #define ff first #define ss second const ll N = 305; const ll M = 1e9 + 7; int T, n, m, k, b[N][N*10], s[N][N*10], dis[N][N]; vector <pair<int,int>> v[N]; int main(){ ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m >> k; for(int i = 1; i <= n; i++){ for(int j = 1; j <= k; j++){ cin >> b[i][j] >> s[i][j]; } } for(int i = 1; i <= m; i++){ int u1, u2, u3; cin >> u1 >> u2 >> u3; v[u1].push_back({u2,u3}); } int ans = 0; for(int i = 1; i <= k; i++){ ans += max(0,s[1][i]-b[1][i]); } for(int i = 1; i <= n; i++){ priority_queue <pair<int,int>> q; for(int j = 1; j <= n; j++) dis[i][j] = 1e9; dis[i][i] = 0; q.push({0,i}); while(!q.empty()){ int w = q.top().ff, x = q.top().ss; w *= (-1); q.pop(); if(dis[i][x] != w) continue; for(auto [w1,j] : v[x]){ if(dis[i][j] > dis[i][x] + w1){ dis[i][j] = dis[i][x] + w1; q.push({-dis[i][j],j}); } } } } int mn = 1e9; for(int i = 2; i <= n; i++){ mn = min(mn, dis[i][1] + dis[1][i]); } if(mn == 1e9 or mn == 0) cout << 0; else cout << (ans/mn); 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...