結果
問題 | No.807 umg tours |
ユーザー |
|
提出日時 | 2023-05-31 02:58:21 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 373 ms / 4,000 ms |
コード長 | 4,089 bytes |
コンパイル時間 | 827 ms |
コンパイル使用メモリ | 85,192 KB |
最終ジャッジ日時 | 2025-02-13 17:01:59 |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 26 |
ソースコード
#include <vector> #include <iostream> #include <algorithm> #include <array> using namespace std; /* * @title RadixHeap - 非負整数heap * @docs md/heap/RadixHeap.md */ template<class T, class Key = unsigned long long> class RadixHeap{ using TypeNode = pair<Key, T>; template<class InnerKey, class ZZ=InnerKey> class Inner{}; template<class InnerKey> class Inner<InnerKey, unsigned long long>{ array<vector<TypeNode>,65> vq; unsigned long long size_num; TypeNode last; inline int bit(unsigned long long a) { return a ? 64 - __builtin_clzll(a) : 0;} public: Inner(T mini) : size_num(0), last(make_pair(0, mini)) {} inline bool empty() { return size_num == 0; } inline size_t size(){ return size_num; } inline void push(TypeNode x){ ++size_num; vq[bit(x.first^last.first)].push_back(x);} inline void emplace(unsigned long long key,T val){ ++size_num; vq[bit(key^last.first)].emplace_back(key,val);} inline TypeNode pop() { if(vq[0].empty()) { int i = 1; while(vq[i].empty()) ++i; last = *min_element(vq[i].begin(),vq[i].end()); for(auto &p : vq[i]) vq[bit(p.first ^ last.first)].push_back(p); vq[i].clear(); } --size_num; auto res = vq[0].back(); vq[0].pop_back(); return res; } }; template<class InnerKey> class Inner<InnerKey, unsigned int>{ array<vector<TypeNode>,33> vq; unsigned int size_num; TypeNode last; inline int bit(unsigned int a) { return a ? 32 - __builtin_clz(a) : 0;} public: Inner(T mini) : size_num(0), last(make_pair(0, mini)) {} inline bool empty() { return size_num == 0; } inline size_t size(){ return size_num; } inline void push(TypeNode x){ ++size_num; vq[bit(x.first^last.first)].push_back(x);} inline void emplace(unsigned int key,T val){ ++size_num; vq[bit(key^last.first)].emplace_back(key,val);} inline TypeNode pop() { if(vq[0].empty()) { int i = 1; while(vq[i].empty()) ++i; last = *min_element(vq[i].begin(),vq[i].end()); for(auto &p : vq[i]) vq[bit(p.first ^ last.first)].push_back(p); vq[i].clear(); } --size_num; auto res = vq[0].back(); vq[0].pop_back(); return res; } }; Inner<Key,Key> inner; public: RadixHeap(T mini) : inner(mini) {} inline bool empty() { return inner.empty();} inline size_t size(){ return inner.size();} inline void push(TypeNode x){ inner.push(x);} inline void emplace(unsigned long long key,T val){ inner.emplace(key,val);} inline TypeNode pop() { return inner.pop(); } }; //Dijkstra template<class T> class Dijkstra { public: int N; T inf; vector<T> cost; vector<vector<pair<T, int>>> edge; Dijkstra(const int N, T inf) : N(N), inf(inf), cost(N), edge(N) { } void make_edge(int from, int to, T w) { edge[from].push_back({ w,to }); } void solve(int start) { for (int i = 0; i < N; ++i) cost[i] = inf; RadixHeap<int,unsigned long long> pq(0); cost[start] = 0; pq.push({ 0,start }); while (!pq.empty()) { auto p = pq.pop(); T v = p.first; int from = p.second; if(cost[from]<v) continue; for (auto u : edge[from]) { T w = v + u.first; int to = u.second; if (w < cost[to]) { cost[to] = w; pq.push({ w,to }); } } } return; } }; int main() { cin.tie(0);ios::sync_with_stdio(false); int N, M; cin >> N >> M; Dijkstra<long long> dijk(2*N, 1LL<<60); for(int i = 0; i < M; ++i){ int a, b; long long c; cin >> a >> b >> c; a--, b--; dijk.make_edge(a, b, c); dijk.make_edge(b, a, c); dijk.make_edge(a+N, b+N, c); dijk.make_edge(b+N, a+N, c); dijk.make_edge(a, b+N, 0); dijk.make_edge(b, a+N, 0); } dijk.solve(0); dijk.cost[N]=0; for (int i = 0; i < N; ++i) cout << dijk.cost[i]+dijk.cost[i+N] << endl; return 0; }