Submission #312757

#TimeUsernameProblemLanguageResultExecution timeMemory
312757KuuhakuTravelling Merchant (APIO17_merchant)C++17
21 / 100
127 ms2284 KiB
#include <cstdio> #include <cctype> #include <cstring> #include <algorithm> #include <vector> typedef long long LL; inline char fgc() { static char buf[100000], *p1 = buf, *p2 = buf; return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++; } inline LL readint() { register LL res = 0, neg = 1; register char c = fgc(); while(!isdigit(c)) { if(c == '-') neg = -1; c = fgc(); } while(isdigit(c)) { res = (res << 1) + (res << 3) + c - '0'; c = fgc(); } return res * neg; } const int MAXN = 105, MAXK = 1005; const LL INF = 0x3f3f3f3f3f3f3f3f; int n, m, K; LL gra[MAXN][MAXN], prof[MAXN][MAXN], b[MAXN][MAXK], s[MAXN][MAXK]; LL dis[MAXN][MAXN]; inline bool check(LL mid) { memset(dis, 0x3f, sizeof(dis)); for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { if(gra[i][j] == INF) continue; dis[i][j] = std::min(INF, gra[i][j] * mid - prof[i][j]); } dis[i][i] = INF; } for(int k = 1; k <= n; k++) { for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { dis[i][j] = std::min(INF, std::min(dis[i][j], dis[i][k] + dis[k][j])); } if(dis[i][i] <= 0) return true; } } return false; } int u, v; LL w; int main() { memset(gra, 0x3f, sizeof(gra)); n = readint(); m = readint(); K = readint(); for(int i = 1; i <= n; i++) { gra[i][i] = 0; for(int j = 1; j <= K; j++) { b[i][j] = readint(); s[i][j] = readint(); } } for(int i = 1; i <= m; i++) { u = readint(); v = readint(); w = readint(); gra[u][v] = std::min(gra[u][v], w); } for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { for(int k = 1; k <= K; k++) { if(b[i][k] == -1 || s[j][k] == -1) continue; prof[i][j] = std::max(prof[i][j], s[j][k] - b[i][k]); } } } for(int k = 1; k <= n; k++) { for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { gra[i][j] = std::min(gra[i][j], gra[i][k] + gra[k][j]); } } } LL l = 0, r = 1e15, mid; while(r - l > 1) { mid = (l + r) >> 1; if(check(mid)) l = mid; else r = mid; } printf("%lld", l); return 0; }

Compilation message (stderr)

merchant.cpp: In function 'LL readint()':
merchant.cpp:16:17: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   16 |     register LL res = 0, neg = 1;
      |                 ^~~
merchant.cpp:16:26: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   16 |     register LL res = 0, neg = 1;
      |                          ^~~
merchant.cpp:17:19: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   17 |     register char c = fgc();
      |                   ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...