結果
問題 | No.1 道のショートカット |
ユーザー |
|
提出日時 | 2019-04-12 20:43:40 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 3 ms / 5,000 ms |
コード長 | 1,904 bytes |
コンパイル時間 | 725 ms |
コンパイル使用メモリ | 89,316 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-20 16:38:32 |
合計ジャッジ時間 | 1,878 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
コンパイルメッセージ
main.cpp: In function ‘int main(int, char**)’: main.cpp:54:20: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 54 | REP(i, m) scanf("%d", &e[i].from), --e[i].from; | ~~~~~^~~~~~~~~~~~~~~~~~ main.cpp:55:20: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 55 | REP(i, m) scanf("%d", &e[i].to), --e[i].to; | ~~~~~^~~~~~~~~~~~~~~~ main.cpp:56:20: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 56 | REP(i, m) scanf("%d", &e[i].price); | ~~~~~^~~~~~~~~~~~~~~~~~~ main.cpp:57:20: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 57 | REP(i, m) scanf("%d", &e[i].cost); | ~~~~~^~~~~~~~~~~~~~~~~~
ソースコード
#include <assert.h> #include <ctype.h> #include <float.h> #include <limits.h> #include <math.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <sys/types.h> #include <algorithm> #include <bitset> #include <complex> #include <iostream> #include <list> #include <map> #include <numeric> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <unordered_map> #include <unordered_set> #include <vector> using namespace std; #define SZ(a) (int)(a).size() #define FOR(i,a,b) for (int i=(a); i<=(b); ++i) #define REP(i,n) for (int i=0; i<(n); ++i) #define ALL(c) c.begin(), c.end() #define CLR(c,n) memset(c, n, sizeof(c)) #define MCPY(d, s) memcpy(d, s, sizeof(d)) #define TR(it, c) for (auto it = c.begin();it != c.end(); ++it) #define CONTAIN(it, c) (c.find(it) != c.end()) typedef vector<int> VI; typedef pair<int, int> PII; template <class T> void checkmin(T &a, T b) { if (b<a) a=b; } template <class T> void checkmax(T &a, T b) { if (b>a) a=b; } typedef long long LL; const int INF=0x3F3F3F3F; const int N=50, M=1500, C=300; struct Edge { int from, to; int price, cost; } e[M]; int head[N], nxt[M]; int dp[N][C+1]; int n, c, m; int main(int argc, char *argv[]) { while (scanf("%d%d%d", &n, &c, &m) != EOF) { REP(i, m) scanf("%d", &e[i].from), --e[i].from; REP(i, m) scanf("%d", &e[i].to), --e[i].to; REP(i, m) scanf("%d", &e[i].price); REP(i, m) scanf("%d", &e[i].cost); CLR(head, -1); REP(i, m) { int d=e[i].to; nxt[i] = head[d]; head[d] = i; } CLR(dp, INF); CLR(dp[0], 0); for (int i = 1; i < n; ++i) { for (int j = head[i]; j >= 0; j = nxt[j]) { for (int c1=0, c2=e[j].price; c2 <= c; ++c1, ++c2) { checkmin(dp[i][c2], dp[e[j].from][c1]+e[j].cost); } } } int ans = dp[n-1][c]; printf("%d\n", ans == INF ? -1 : ans); } }