제출 #684430

#제출 시각아이디문제언어결과실행 시간메모리
684430ar88lo여행하는 상인 (APIO17_merchant)C++14
0 / 100
62 ms3276 KiB
#include <bits/stdc++.h> #define int long long using namespace std; const int INF = 1e9+1; int n,m,k; int dis[101][101], adj[101][101], adj2[101][101], prof[101][101]; int s[101][1001],b[101][1001]; bool check(int c){ for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ adj2[i][j] = prof[i][j] - c * adj[i][j]; if(adj[i][j] == INF) adj2[i][j] = c * INF; } } for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ dis[i][j] = adj2[i][j];}} for(int x = 1; x <= n; x++){ for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ if(dis[i][x] < c * INF && dis[x][j] < c * INF) dis[i][j] = min(dis[i][j], dis[i][x] + dis[x][j]); } } } for(int i = 1; i <= n; i++){ if(dis[i][i] >= 0) return 1; } return 0; } int32_t main(){ cin>>n>>m>>k; for(int i = 1; i <= n; i++){ for(int j = 0; j < k; j++){ cin>>b[i][j]>>s[i][j]; } } for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ adj[i][j] = INF; } } for(int i = 0; i < m; i++){ int u,v,w; cin>>u>>v>>w; adj[u][v] = w; } for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ for(int x = 0; x < k; x++){ if(s[j][x] != -1 && b[i][x] != -1){ prof[i][j] = max(prof[i][j], s[j][x] - b[i][x]); } } } } int ans = -1; for(int x = 1e9; x > 0; x/=2){ while(ans + x < 1e9 && check(ans+x)) ans+=x; } cout<<ans + 1<<'\n'; 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...