# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
106196 | 2019-04-17T09:05:00 Z | ekrem | 여행하는 상인 (APIO17_merchant) | C++ | 439 ms | 1336 KB |
#include <bits/stdc++.h> #define st first #define nd second #define mp make_pair #define pb push_back #define orta ((bas+son+1)/2) #define inf 1000000000000007ll #define N 1005 using namespace std; typedef long long ll; typedef pair < int , int > ii; ll n, m, k, mx, bas, son, a[N][N], d[105][105], dd[105][105]; bool yap(int x){ for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++){ if(i == j){ dd[i][i] = -inf; continue; } mx = 0; for(int y = 1; y <= k+k; y += 2) if(a[i][y] != -1 and a[j][y + 1] != -1) mx = max(mx, a[j][y + 1] - a[i][y]); dd[i][j] = mx - x*d[i][j]; // cout << i << " " << j << " " << d[i][j] << " " << mx << endl; } for(int k = 1; k <= n; k++) for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) dd[i][j] = max(dd[i][j], min(inf, dd[i][k] + dd[k][j]) ); // for(int i = 1; i <= n; i++) // for(int j = 1; j <= n; j++) // cout << i << " " << j << " " << dd[i][j] << endl; for(int i = 1; i <= n; i++) if(dd[i][i] >= 0) return true; return false; } int main() { // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); scanf("%lld %lld %lld",&n ,&m ,&k); for(int i = 1; i <= n; i++) for(int j = 1; j <= k+k; j++) scanf("%lld",&a[i][j]); for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++){ d[i][j] = inf; d[i][i] = 0; } for(int i = 1; i <= m; i++){ ll x, y, z; scanf("%lld %lld %lld",&x ,&y ,&z); d[x][y] = min(d[x][y], z); } for(int k = 1; k <= n; k++) for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) d[i][j] = min(d[i][j], d[i][k] + d[k][j]); // yap(2); // cout << yap(4) << endl; bas = 0, son = 1000000007; while(bas < son){ if(yap(orta)) bas = orta; else son = orta - 1; } printf("%lld\n", orta); return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 439 ms | 1272 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 12 ms | 640 KB | Output is correct |
2 | Correct | 11 ms | 700 KB | Output is correct |
3 | Correct | 17 ms | 640 KB | Output is correct |
4 | Correct | 15 ms | 680 KB | Output is correct |
5 | Correct | 19 ms | 640 KB | Output is correct |
6 | Correct | 2 ms | 384 KB | Output is correct |
7 | Incorrect | 10 ms | 768 KB | Output isn't correct |
8 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 98 ms | 1024 KB | Output is correct |
2 | Incorrect | 411 ms | 1336 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 12 ms | 640 KB | Output is correct |
2 | Correct | 11 ms | 700 KB | Output is correct |
3 | Correct | 17 ms | 640 KB | Output is correct |
4 | Correct | 15 ms | 680 KB | Output is correct |
5 | Correct | 19 ms | 640 KB | Output is correct |
6 | Correct | 2 ms | 384 KB | Output is correct |
7 | Incorrect | 10 ms | 768 KB | Output isn't correct |
8 | Halted | 0 ms | 0 KB | - |