結果
問題 | No.1283 Extra Fee |
ユーザー | ok |
提出日時 | 2020-11-06 22:39:38 |
言語 | C++14 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 162 ms / 2,000 ms |
コード長 | 2,233 bytes |
コンパイル時間 | 1,190 ms |
コンパイル使用メモリ | 96,700 KB |
実行使用メモリ | 23,748 KB |
最終ジャッジ日時 | 2023-08-10 06:03:09 |
合計ジャッジ時間 | 4,735 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,380 KB |
testcase_01 | AC | 1 ms
4,380 KB |
testcase_02 | AC | 1 ms
4,380 KB |
testcase_03 | AC | 1 ms
4,380 KB |
testcase_04 | AC | 1 ms
4,380 KB |
testcase_05 | AC | 1 ms
4,380 KB |
testcase_06 | AC | 2 ms
4,380 KB |
testcase_07 | AC | 2 ms
4,384 KB |
testcase_08 | AC | 2 ms
4,376 KB |
testcase_09 | AC | 2 ms
4,376 KB |
testcase_10 | AC | 1 ms
4,376 KB |
testcase_11 | AC | 7 ms
4,468 KB |
testcase_12 | AC | 10 ms
4,380 KB |
testcase_13 | AC | 7 ms
4,380 KB |
testcase_14 | AC | 28 ms
5,896 KB |
testcase_15 | AC | 44 ms
7,616 KB |
testcase_16 | AC | 10 ms
4,380 KB |
testcase_17 | AC | 121 ms
22,544 KB |
testcase_18 | AC | 148 ms
17,884 KB |
testcase_19 | AC | 155 ms
18,412 KB |
testcase_20 | AC | 148 ms
17,576 KB |
testcase_21 | AC | 152 ms
17,768 KB |
testcase_22 | AC | 133 ms
15,948 KB |
testcase_23 | AC | 128 ms
18,964 KB |
testcase_24 | AC | 144 ms
18,944 KB |
testcase_25 | AC | 162 ms
19,108 KB |
testcase_26 | AC | 158 ms
18,844 KB |
testcase_27 | AC | 160 ms
18,836 KB |
testcase_28 | AC | 161 ms
18,948 KB |
testcase_29 | AC | 126 ms
23,748 KB |
ソースコード
#include<iostream> #include<string> #include<iomanip> #include<cmath> #include<vector> #include<algorithm> #include<utility> #include<queue> using namespace std; #define int long long #define endl "\n" constexpr long long INF = (long long)1e18; constexpr long long MOD = 1'000'000'007; struct fast_io { fast_io(){ std::cin.tie(nullptr); std::ios::sync_with_stdio(false); }; } fio; int N, M; vector<vector<int>> cost; struct Node{ int y, x, z, c; bool operator > (const Node &n) const { return c > n.c; } }; int dx[] = {0, 0, 1, -1}; int dy[] = {1, -1, 0, 0}; int dijkstra(){ priority_queue<Node, vector<Node>, greater<Node>> Q; vector<vector<vector<int>>> d(N, vector<vector<int>>(N, vector<int>(2, INF))); Q.push({0, 0, 0, 0}); d[0][0][0] = 0; while(Q.size()){ Node cur = Q.top(); Q.pop(); // cout<<cur.y<<" "<<cur.x<<" z = "<<cur.z<<endl; // cout<<d[cur.y][cur.x][cur.z]<<" [][] "<<cur.c<<endl; if(d[cur.y][cur.x][cur.z] < cur.c) continue; if(cur.y == N-1 && cur.x == N-1) { return cur.c; } // cout<<cur.y<<" "<<cur.x<<endl; for(int i = 0; i < 4; i++){ int y = dy[i] + cur.y, x = dx[i] + cur.x; if(y < 0 || y >= N || x < 0 || x >= N) continue; if(cur.z == 0) { if(cur.c + 1 < d[y][x][cur.z+1]) { d[y][x][cur.z+1] = cur.c + 1; Q.push({y, x, cur.z + 1, cur.c + 1}); } } // cout<<"i = "<<i<<endl; if(cur.c + 1 + cost[y][x] < d[y][x][cur.z]) { d[y][x][cur.z] = cur.c + 1 + cost[y][x]; // cout<<"<>"<<" y = "<<y<<" x = "<<x<<" "<<d[y][x][cur.z]<<endl; Q.push({y, x, cur.z, d[y][x][cur.z]}); } } } return -1; } signed main(){ cout<<fixed<<setprecision(10); cin>>N>>M; cost.resize(N, vector<int>(N)); for(int i = 0; i < M; i++){ int h, w, c; cin>>h>>w>>c; h--, w--; cost[h][w] = c; } cout<<dijkstra()<<endl; return 0; }