結果
問題 | No.614 壊れたキャンパス |
ユーザー | tnakao0123 |
提出日時 | 2017-12-17 23:25:44 |
言語 | C++11 (gcc 11.4.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,700 bytes |
コンパイル時間 | 841 ms |
コンパイル使用メモリ | 88,740 KB |
実行使用メモリ | 16,568 KB |
最終ジャッジ日時 | 2024-05-09 10:57:09 |
合計ジャッジ時間 | 6,642 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 5 ms
13,952 KB |
testcase_01 | AC | 5 ms
8,320 KB |
testcase_02 | AC | 4 ms
8,320 KB |
testcase_03 | AC | 3 ms
8,320 KB |
testcase_04 | AC | 4 ms
8,448 KB |
testcase_05 | AC | 5 ms
8,320 KB |
testcase_06 | AC | 4 ms
8,448 KB |
testcase_07 | AC | 4 ms
8,320 KB |
testcase_08 | AC | 77 ms
10,752 KB |
testcase_09 | AC | 74 ms
11,612 KB |
testcase_10 | AC | 103 ms
11,392 KB |
testcase_11 | AC | 98 ms
10,624 KB |
testcase_12 | AC | 112 ms
10,880 KB |
testcase_13 | AC | 100 ms
10,752 KB |
testcase_14 | AC | 82 ms
11,008 KB |
testcase_15 | AC | 81 ms
11,008 KB |
testcase_16 | AC | 79 ms
11,904 KB |
testcase_17 | AC | 86 ms
14,592 KB |
testcase_18 | TLE | - |
testcase_19 | -- | - |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:54:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 54 | scanf("%d%d%d%d%d", &n, &m, &k, &st, &gl); | ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ main.cpp:58:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 58 | scanf("%d%d%d", &ai, &bi, &ci); | ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
ソースコード
/* -*- coding: utf-8 -*- * * 614.cc: No.614 壊れたキャンパス - yukicoder */ #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<iostream> #include<string> #include<vector> #include<map> #include<set> #include<stack> #include<list> #include<queue> #include<deque> #include<algorithm> #include<numeric> #include<utility> #include<complex> #include<functional> using namespace std; /* constant */ const int MAX_N = 200000; const int MAX_M = 200000; typedef long long ll; const ll LINF = 1LL << 60; /* typedef */ typedef pair<int,int> pii; typedef vector<pii> vpii; /* global variables */ vpii nbrs[MAX_N]; ll dp[2][MAX_M]; /* subroutines */ inline ll absll(ll a) { return (a >= 0) ? a : -a; } inline void setmin(ll &a, ll b) { if (a > b) a = b; } /* main */ int main() { int n, m, k, st, gl; scanf("%d%d%d%d%d", &n, &m, &k, &st, &gl); for (int i = 0; i < m; i++) { int ai, bi, ci; scanf("%d%d%d", &ai, &bi, &ci); nbrs[ai].push_back(pii(bi, ci)); } nbrs[0].push_back(pii(0, st)); dp[0][0] = 0; int cur = 0, nxt = 1; for (int i = 1; i < n; i++) { vpii &nbr0 = nbrs[i - 1], &nbr1 = nbrs[i]; if (nbr1.empty()) { puts("-1"); return 0; } int n0 = nbr0.size(), n1 = nbr1.size(); fill(dp[nxt], dp[nxt] + n1, LINF); for (int j0 = 0; j0 < n0; j0++) { int &f0 = nbr0[j0].second; for (int j1 = 0; j1 < n1; j1++) setmin(dp[nxt][j1], dp[cur][j0] + absll(nbr1[j1].first - f0)); } cur ^= 1, nxt ^= 1; } ll mind = LINF; for (int j = 0; j < nbrs[n - 1].size(); j++) setmin(mind, dp[cur][j] + absll(gl - nbrs[n - 1][j].second)); printf("%lld\n", mind); return 0; }