제출 #52090

#제출 시각아이디문제언어결과실행 시간메모리
52090Angelos여행하는 상인 (APIO17_merchant)C++14
21 / 100
236 ms1164 KiB
#include <iostream> #include <cstring> #define MAXN 103 #define MAXK 1003 const long long INF = 1e10; using namespace std; typedef long long ll; int N , M , K , T[MAXN][MAXN] ; long long profit[MAXN][MAXN] , adj[MAXN][MAXN] , adj2[MAXN][MAXN] , B[MAXN][MAXN] , S[MAXN][MAXN] , dist[MAXN][MAXN]; bool check(int x){ for(int i=1; i<=N; i++){ for(int j=1; j<=N; j++){ if(i == j || dist[i][j] == INF){adj[i][j] = -INF; continue;} adj[i][j] = (ll)profit[i][j] - (ll)dist[i][j]*x; adj[i][j] = max(-INF, adj[i][j]); } } for(int k=1; k<=N; k++) for(int i=1; i<=N; i++) for(int j=1; j<=N; j++){ adj[i][j] = max(adj[i][j] , adj[i][k] + adj[k][j]); if(adj[i][i] >= 0) return true; adj[i][j] = min(INF , adj[i][j]); adj2[i][j] = adj[i][j]; } /*cout << endl; for(int i=1; i<=N; i++){ for(int j=1; j<=N; j++) cout << adj[i][j] << " " ; cout << endl; } cout << endl;*/ for(int k=1; k<=N; k++) for(int i=1; i<=N; i++) for(int j=1; j<=N; j++){ adj2[i][j] = max(adj2[i][j] , adj2[i][k] + adj2[k][j]); if(adj2[i][j] > adj[i][j]) return true; } return false; } int main(){ cin >> N >> M >> K; for(int i=1; i<=N; i++) for(int k=0; k<K; k++) cin >> B[i][k] >> S[i][k]; for(int i=0; i<=N; i++) for(int j=0; j<=N; j++) dist[i][j] = INF; for(int i=1; i<=N; i++) dist[i][i] = 0; for(int i=0; i<M; i++){ int u,v; cin >> u >> v; cin >> dist[u][v]; } for(int k=1; k<=N; k++) for(int i=1; i<=N; i++) for(int j=1; j<=N; j++) dist[i][j] = min(dist[i][j] , dist[i][k] + dist[k][j]); for(int i=1; i<=N; i++) for(int j=1; j<=N; j++){ profit[i][j] = 0; for(int k=0; k<K; k++){ if(B[i][k] == -1 || S[j][k] == -1) continue; profit[i][j] = max(profit[i][j] , S[j][k] - B[i][k]); } } /*for(int i=1; i<=N; i++){ for(int j=1; j<=N; j++) cout << dist[i][j] << " " ; cout << endl; }*/ long long low = 1 , high = 1e9 + 1 , ANS = 0; while(low <= high){ ll mid = (low + high)/2; //cout << low << " " << mid << " " << high << endl; if(check(mid)) {ANS = max(ANS , mid); low = mid + 1;} else high = mid - 1; } cout << ANS << 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...