# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
59130 | 2018-07-20T15:39:02 Z | wilwxk | Travelling Merchant (APIO17_merchant) | C++11 | 1000 ms | 2040 KB |
#include <bits/stdc++.h> using namespace std; const int MAXN=105; const int MAXK=1005; const long long INF=1e15+9; long long v[MAXN][MAXK][2]; long long dist[MAXN][MAXN], prof[MAXN][MAXN]; long long g[MAXN][MAXN]; bool chega[MAXN][MAXN]; int n, m, k; void floyd() { for(int kk=1; kk<=n; kk++) { for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) { if(chega[i][kk]==0||chega[kk][j]==0) continue; dist[i][j]=min(dist[i][j], dist[i][kk]+dist[kk][j]); chega[i][j]=1; } } } } bool testa(long long x) { for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) { if(chega[i][j]==0) continue; g[i][j]=(x*dist[i][j])-prof[i][j]; } } for(int kk=1; kk<=n; kk++) { for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) { if(chega[i][kk]==0||chega[kk][j]==0) continue; g[i][j]=min(g[i][j], g[i][kk]+g[kk][j]); } } } for(int i=1; i<=n; i++) if(chega[i][i]&&g[i][i]<=0) return 1; return 0; } int main() { scanf("%d %d %d", &n, &m, &k); for(int i=1; i<=n; i++) for(int j=1; j<=k; j++) scanf("%lld %lld", &v[i][j][0], &v[i][j][1]); while(m--) { int a, b, c; scanf("%d %d %d", &a, &b, &c); dist[a][b]=c; chega[a][b]=1; } floyd(); for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) { for(int kk=1; kk<=k; kk++) { if(!chega[i][j]) continue; if(v[i][kk][0]==-1||v[j][kk][1]==-1) continue;//||v[j][kk][1]<v[i][kk][0]) continue; prof[i][j]=max(prof[i][j], v[j][kk][1]-v[i][kk][0]); } } } long long resp=0; for(long long i=1e9+1; i>0; i/=2) while(testa(resp+i)) resp+=i; printf("%lld\n", resp); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1086 ms | 2040 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1064 ms | 2040 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1077 ms | 2040 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1064 ms | 2040 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |