結果
問題 | No.160 最短経路のうち辞書順最小 |
ユーザー | 小指が強い人 |
提出日時 | 2016-09-20 23:36:47 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 25 ms / 5,000 ms |
コード長 | 6,281 bytes |
コンパイル時間 | 2,494 ms |
コンパイル使用メモリ | 195,252 KB |
実行使用メモリ | 6,988 KB |
最終ジャッジ日時 | 2024-11-17 10:16:38 |
合計ジャッジ時間 | 3,991 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,248 KB |
testcase_02 | AC | 2 ms
5,248 KB |
testcase_03 | AC | 2 ms
5,248 KB |
testcase_04 | AC | 6 ms
5,248 KB |
testcase_05 | AC | 10 ms
5,248 KB |
testcase_06 | AC | 14 ms
5,456 KB |
testcase_07 | AC | 4 ms
5,248 KB |
testcase_08 | AC | 4 ms
5,248 KB |
testcase_09 | AC | 4 ms
5,248 KB |
testcase_10 | AC | 5 ms
5,248 KB |
testcase_11 | AC | 5 ms
5,248 KB |
testcase_12 | AC | 4 ms
5,248 KB |
testcase_13 | AC | 4 ms
5,248 KB |
testcase_14 | AC | 4 ms
5,248 KB |
testcase_15 | AC | 4 ms
5,248 KB |
testcase_16 | AC | 4 ms
5,248 KB |
testcase_17 | AC | 4 ms
5,248 KB |
testcase_18 | AC | 4 ms
5,248 KB |
testcase_19 | AC | 4 ms
5,248 KB |
testcase_20 | AC | 4 ms
5,248 KB |
testcase_21 | AC | 4 ms
5,248 KB |
testcase_22 | AC | 4 ms
5,248 KB |
testcase_23 | AC | 4 ms
5,248 KB |
testcase_24 | AC | 5 ms
5,248 KB |
testcase_25 | AC | 4 ms
5,248 KB |
testcase_26 | AC | 4 ms
5,248 KB |
testcase_27 | AC | 2 ms
5,248 KB |
testcase_28 | AC | 25 ms
6,988 KB |
testcase_29 | AC | 3 ms
5,248 KB |
ソースコード
#include "bits/stdc++.h" using namespace std; typedef long long ll; typedef unsigned long long ull; typedef vector<int> veci; typedef vector<ll> vecll; typedef vector<string> vecs; template<class T,class U> using Hash=unordered_map<T,U>; #define REP(i, a, n) for(ll i = a; i < (ll)(n); i++) #define RREP(i, a, n) for(ll i = n-1; i >= (ll)(a); i--) #define rep(i, n) REP(i, 0, n) #define rrep(i, n) RREP(i, 0, n) #define MD 1000000007 #define _SPLIT " " template<class T> T read(){T a;cin >> a;return a;} template<class T> void read(T& a){cin >> a;} template<class T,class ...Args> void read(T& a, Args&... args){cin >> a; read(args...);} template<class T> void rarr(T a, int n){for(int i = 0; i < n; i++) {cin >> a[i];}} template<class T> void write(T a){cout << setprecision(12) << a << endl;} template<class T,class ...Args> void write(T a, Args... args){cout << setprecision(12) << a << _SPLIT; write(args...);} template<class T> void warr(vector<T> a, const char* c = " "){cout << a[0];for(int i = 1; i < (int)a.size(); i++)cout << c << a[i];cout << endl;;} template<class T> void warr(T a, int n, const char* c = " "){cout << a[0];for(int i = 1; i < n; i++)cout << c << a[i];cout << endl;} void split(string s, string delim, veci& result){result.clear();string::size_type pos = 0;while(pos != string::npos){string::size_type p = s.find(delim, pos);if(p == string::npos){result.push_back(atoi(s.substr(pos).data()));break;}else {result.push_back(atoi(s.substr(pos, p - pos).data()));}pos = p + delim.size();}} void split(string s, string delim, vecs& result){result.clear();string::size_type pos = 0;while(pos != string::npos){string::size_type p = s.find(delim, pos);if(p == string::npos){result.push_back(s.substr(pos));break;}else {result.push_back(s.substr(pos, p - pos));}pos = p + delim.size();}} ll gcd(ll a, ll b){while(true){ll k = a % b;if(k == 0)return b;a = b;b = k;}} ll comb(ll n, ll m){ll p=1;m=min(m,n-m);for(ll i=1;i<=m;i++){p*=n-i+1;p/=i;}return p;} typedef pair<int,vector<int>> my_pair; bool operator<(vector<int>& a,vector<int>& b){ int size=min(a.size(),b.size()); for(int i=0;i<size;i++){ if(a[i]<b[i])return true; else if(a[i]>b[i])return false; } return (int)a.size()==size; } struct WeightedStaticGraph { typedef int Vertex; typedef my_pair Weight; typedef my_pair Dist; static const Dist InfDist; struct To { Vertex to; Weight w; To() { } To(Vertex to_, Weight w_): to(to_), w(w_) { } }; typedef std::pair<Vertex,To> Edge; typedef const To *const_iterator; void init(int n_, const std::vector<Edge> &edges) { n = n_; int m = edges.size(); tos.resize(m+1); offsets.resize(n+1); for(int e = 0; e < m; e ++) offsets[edges[e].first] ++; for(int v = 1; v <= n_; v ++) offsets[v] += offsets[v-1]; for(int e = 0; e < m; e ++) tos[-- offsets[edges[e].first]] = edges[e].second; } int numVertices() const { return n; } inline const_iterator edgesBegin(int v) const { return &tos[offsets[v]]; } inline const_iterator edgesEnd(int v) const { return &tos[offsets[v+1]]; } private: int n; std::vector<To> tos; std::vector<int> offsets; }; const WeightedStaticGraph::Dist WeightedStaticGraph::InfDist(0x7fffffffffffffffLL,vector<int>({100})); typedef WeightedStaticGraph Graph; template<typename Value, typename Compare = std::less<Value>, typename Index = int> class BinaryHeap { Compare cmp; vector<Value> a; vector<Index> idx, nodeidx; int pos; public: BinaryHeap(Compare cmp_ = Compare()): cmp(cmp_) { } BinaryHeap(int n, Compare cmp_ = Compare()): cmp(cmp_) { init(n); } void init(int n) { a.resize(n+1); idx.assign(n+1, -1); nodeidx.assign(n+1, -1); pos = 1; } const Value &min() const { return a[1]; } const Value &get(Index i) const { return a[nodeidx[i]]; } Index argmin() const { return idx[1]; } Index size() const { return pos - 1; } bool empty() const { return pos == 1; } const Value &add(Index i, const Value &x) { Index node = nodeidx[i]; if(node >= 0) return a[node]; a[pos] = x; idx[pos] = i; nodeidx[i] = pos; ++ pos; up(pos-1); return x; } const Value &update(Index i, const Value &x) { Index node = nodeidx[i]; if(node < 0) { a[pos] = x; idx[pos] = i; nodeidx[i] = pos; ++ pos; up(pos-1); }else { a[node] = x; up(node); down(node); } return x; } const Value &updatemin(Index i, const Value &x) { Index node = nodeidx[i]; if(node >= 0 && !cmp(x, a[node])) return a[node]; else return update(i, x); } const Value remove(Index i) { if(i < 0) return Value(); Index node = nodeidx[i]; if(node < 0) return Value(); -- pos; idx[node] = idx[pos]; nodeidx[idx[pos]] = node; nodeidx[i] = -1; idx[pos] = -1; swap(a[pos], a[node]); up(node); down(node); return a[pos]; } private: void up(Index i) { for(Index c = i, p = c >> 1; p > 0 && cmp(a[c], a[p]); c >>= 1, p >>= 1) { swap(a[p], a[c]); swap(nodeidx[idx[p]], nodeidx[idx[c]]); swap(idx[p], idx[c]); } } void down(Index i) { Index bottom = pos; for(Index c = i; c * 2 < bottom; ) { Index b = c * 2 + (c * 2 + 1 < bottom && cmp(a[c * 2 + 1], a[c * 2])); if(!cmp(a[b], a[c])) break; swap(a[c], a[b]); swap(nodeidx[idx[c]], nodeidx[idx[b]]); swap(idx[c], idx[b]); c = b; } } }; void dijkstra(const Graph &g, int s, vector<Graph::Dist> &dist) { int n = g.numVertices(); dist.assign(n, Graph::InfDist); vector<bool> vis(n); BinaryHeap<Graph::Dist> h(n); h.add(s, my_pair(0,vector<int>({s}))); while(!h.empty()) { int v = h.argmin(); dist[v] = h.get(v); h.remove(v); vis[v] = true; for(Graph::const_iterator it = g.edgesBegin(v), et = g.edgesEnd(v); it != et; ++ it) { if(!vis[it->to]){ vector<int> t=dist[v].second; t.push_back(it->to); h.updatemin(it->to, my_pair(dist[v].first + it->w.first,t)); } } } } int main(void) { int n,m,s,g; vector<Graph::Edge> e; Graph gr; read(n,m,s,g); rep(i,m){ Graph::Edge p; read(p.first,p.second.to,p.second.w.first); e.push_back(p); swap(p.first,p.second.to); e.push_back(p); } gr.init(n,e); vector<Graph::Dist> dist; dijkstra(gr, s, dist); warr(dist[g].second); return 0; }