結果
問題 | No.496 ワープクリスタル (給料日前編) |
ユーザー |
![]() |
提出日時 | 2017-03-25 00:15:58 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 3 ms / 2,000 ms |
コード長 | 1,080 bytes |
コンパイル時間 | 1,144 ms |
コンパイル使用メモリ | 79,308 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-06 03:10:52 |
合計ジャッジ時間 | 3,391 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 23 |
ソースコード
#include <iostream> #include <string> #include <vector> #include <map> #include <algorithm> using namespace std; struct POS { int x, y; bool operator<(const POS &right)const { if (x + y != right.x + right.y)return x + y > right.x + right.y; return x > right.x; } }; int main() { int Gx, Gy, N, F;cin >> Gx >> Gy >> N >> F; vector<pair<int,POS>>xyc(N); for (int i = 0;i < N;i++) { cin >> xyc[i].second.x >> xyc[i].second.y >> xyc[i].first; } sort(xyc.begin(), xyc.end()); map<POS, int>M; POS p = { 0,0 }; M[p] = 0; for (int i = 0;i < N;i++) { for (auto itr = M.begin();itr != M.end();itr++) { POS pos = itr->first; pos.x += xyc[i].second.x;pos.y += xyc[i].second.y; if (pos.x > Gx || pos.y > Gy)continue; if (M.find(pos) == M.end()) { M[pos] = itr->second + xyc[i].first; } else M[pos] = min(M[pos], itr->second + xyc[i].first); } } int ans = 1e8; for (auto itr = M.begin();itr != M.end();itr++) { ans = min(ans, itr->second + F*abs(itr->first.x - Gx) + F*abs(itr->first.y - Gy)); } cout << ans << endl; return 0; }