結果
問題 | 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(); }};//Dijkstratemplate<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;}