結果
問題 | No.1449 新プロランド |
ユーザー |
![]() |
提出日時 | 2021-03-31 14:19:19 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 13 ms / 2,000 ms |
コード長 | 1,144 bytes |
コンパイル時間 | 1,971 ms |
コンパイル使用メモリ | 174,416 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-12-24 01:43:45 |
合計ジャッジ時間 | 2,847 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#include <bits/stdc++.h> int ri() { int n; scanf("%d", &n); return n; } template<typename T> using pqueue_inv = std::priority_queue<T, std::vector<T>, std::greater<T> >; #define MUL 1002 int main() { int n = ri(); int m = ri(); std::vector<std::pair<int, int> > hen[n]; for (int i = 0; i < m; i++) { int a = ri() - 1; int b = ri() - 1; int c = ri(); hen[a].push_back({b, c}); hen[b].push_back({a, c}); } int needed[n]; for (auto &i : needed) i = ri(); std::vector<int> dist(MUL * n, 1000000000); pqueue_inv<std::pair<int, int> > que; que.push({dist[0] = 0, 0}); while (que.size()) { auto i = que.top(); que.pop(); if (i.first != dist[i.second]) continue; int id = i.second / MUL; int p = std::min(i.second % MUL + needed[id], MUL - 1); // std::cerr << id << " " << p << " " << i.first << std::endl; i.first += needed[id]; for (auto j : hen[id]) { int64_t next_dist = i.first + j.second / p; if (dist[j.first * MUL + p] > next_dist) que.push({dist[j.first * MUL + p] = next_dist, j.first * MUL + p}); } } printf("%d\n", *std::min_element(dist.end() - MUL, dist.end())); return 0; }