結果
問題 | No.807 umg tours |
ユーザー |
|
提出日時 | 2019-03-22 23:08:50 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 3,425 bytes |
コンパイル時間 | 1,915 ms |
コンパイル使用メモリ | 182,644 KB |
実行使用メモリ | 29,892 KB |
最終ジャッジ日時 | 2024-11-23 19:08:59 |
合計ジャッジ時間 | 11,738 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 25 TLE * 1 |
ソースコード
#include "bits/stdc++.h" using namespace std; /* macro */ #define rep(i,a,b) for(int i=a;i<b;i++) #define revrep(i,a,b) for(int i = a; i > b; i--) #define int long long #define exist(s,e) ((s).find(e)!=(s).end()) #define all(v) (v).begin(), (v).end() #define each(s,itr) for(auto (itr) = s.begin(); (itr) != s.end(); (itr)++) #define sum(v) accumulate(all(v), (0LL)) #define isin(a, b, c) (b <= a && a <= c) #define println cout << "\n"; #define sz(v) (int)v.size() #define bin(x) static_cast<bitset<16> >(x) /* alias */ template<class T> using vec = vector<T>; typedef vector<int> vi; typedef pair<int, int> pi; typedef tuple<int, int, int> ti; typedef map<int, int> mi; typedef set<int> si; /* constant */ const int inf = 1LL << 62; const int mod = 1e9 + 7; const int dx[8]={1,0,-1,0,-1,1,-1,1}; const int dy[8]={0,1,0,-1,-1,-1,1,1}; const string alphabet = "abcdefghijklmnopqrstuvwxyz"; /* io_method */ int input(){int tmp;cin >> tmp;return tmp;} string raw_input(){string tmp;cin >> tmp;return tmp;} template<class T> void printx(T n){cout << n;} template<class T, class U> void printx(pair<T, U> p){cout << "(" << p.first << "," << p.second << ")";} template<class T, class U, class V> void printx(tuple<T, U, V> t){cout << "{" << get<0>(t) << "," << get<1>(t) <<"," << get<2>(t) << "}" << endl;} template<class T> void printx(vector<T> v){cout << "{";rep(i,0,v.size()){printx(v[i]);if(i != v.size()-1)printx(",");}cout << "}";} template<class T> void print(T n){printx(n);cout << endl;} template<class T> void print(set<T> s){cout << "{";each(s, e){if(e != s.begin()) printx(",");printx(*e);}cout << "}" << endl;} template<class T, class U> void print(map<T, U> mp){cout << "{";each(mp, e){cout << "(" << e -> first << "," << e -> second << ")";}cout << "}" << endl;} template<class T> void printans(vec<T> v){rep(i,0,sz(v)){cout << v[i] << (i == sz(v) - 1 ? "" : " ");}cout << endl;} /* general_method */ template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; } template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; } template<class T>T cut(T &a, int l, int r){return T(a.begin()+l, a.begin()+r);} /* main */ int n, m; vec<vec<pi>>edges(101010); void in(){ cin >> n >> m; rep(i,0,m){ int f, t, c; cin >> f >> t >> c; f--; t--; edges[f].push_back(pi(t, c)); edges[t].push_back(pi(f, c)); } } void solve(){ vi dist(n, inf); vi use0(n, inf); priority_queue<ti, vec<ti>, greater<ti>> que; que.push(ti(0, 0, false)); dist[0] = 0; use0[0] = 0; while(not que.empty()){ int d = get<0>(que.top()); int v = get<1>(que.top()); bool isuse = get<2>(que.top()); que.pop(); if(dist[v] < d) continue; rep(i,0,sz(edges[v])){ int nxt = edges[v][i].first; int len = edges[v][i].second; if(!isuse && chmin(dist[nxt], d + len)){ que.push(ti(dist[nxt], nxt, isuse)); } if(!isuse && chmin(use0[nxt], d)){ que.push(ti(use0[nxt], nxt, true)); } if(isuse && chmin(use0[nxt], d + len)){ que.push(ti(use0[nxt], nxt, true)); } } } rep(i,0,n){ print(dist[i] + use0[i]); } } signed main(){ cin.tie(0); ios::sync_with_stdio(false); in(); solve(); }