結果

問題 No.807 umg tours
ユーザー kurarrrkurarrr
提出日時 2019-03-22 22:03:46
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 365 ms / 4,000 ms
コード長 4,910 bytes
コンパイル時間 1,880 ms
コンパイル使用メモリ 206,996 KB
最終ジャッジ日時 2025-01-06 23:50:55
ジャッジサーバーID
(参考情報)
judge4 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#ifdef DEBUG_IS_VALID
#define DEB 1
#define _LIBCPP_DEBUG 0
#else
#define DEB 0
#define NDEBUG
#endif
#include "bits/stdc++.h"
#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i, x, n) for(int i = x; i >= n; i--)
#define rrep(i, n) RREP(i,n,0)
#define pb push_back
#pragma GCC optimize ("-O3")
using namespace std;
#define DUMPOUT cout
#define dump(...) if(DEB) DUMPOUT<<" "<<#__VA_ARGS__<<" :["<<__LINE__<<":"<<__FUNCTION__<<"]"<<endl<<" "; if(DEB) dump_func(__VA_ARGS__)
template<typename T1,typename T2>ostream& operator << (ostream& os, pair<T1,T2> p){cout << "(" << p.first << ", " << p.second << ")"; return os;}
template<typename T>ostream& operator << (ostream& os, vector<T>& vec) { os << "{"; for (int i = 0; i<vec.size(); i++) os << vec[i] << (i + 1 == vec
    .size() ? "" : ", "); os << "}"; return os; }
template<typename T>ostream& operator << (ostream& os, set<T>& st){cout << "{"; for(auto itr = st.begin(); itr != st.end(); itr++) cout << *itr <<
    (next(itr)!=st.end() ? ", " : ""); cout << "}"; return os;}
template<typename T1,typename T2>ostream& operator << (ostream& os, map<T1,T2> mp){cout << "{"; for(auto itr = mp.begin(); itr != mp.end(); itr++)
    cout << "(" << (itr->first) << ", " << (itr->second) << ")" << (next(itr)!=mp.end() ? "," : ""); cout << "}"; return os; }
void dump_func(){DUMPOUT << endl;}
template <class Head, class... Tail>void dump_func(Head&& head, Tail&&... tail){ DUMPOUT << head; if (sizeof...(Tail) == 0) { DUMPOUT << " "; } else
    { DUMPOUT << ", "; } dump_func(std::move(tail)...);}
template<class T> inline bool chmax(T& a,T const& b){if(a>=b) return false; a=b; return true;}
template<class T> inline bool chmin(T& a,T const& b){if(a<=b) return false; a=b; return true;}
void _main();
int main(){ cin.tie(0); ios::sync_with_stdio(false); _main(); return 0;}
using ll = long long;
using P = pair<int,int>;
using Pl = pair<ll,ll>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
const int mod=1e9+7,INF=1<<29;
const double EPS=1e-5,PI=3.1415926535897932384626;
const ll lmod = 1e9+7,LINF=1LL<<59;
using vd = vector<double>;
using vvd = vector<vd>;
namespace sub {
template <typename T>
constexpr typename std::enable_if<std::is_integral<T>::value, T>::type
inf_sub() {
return std::numeric_limits<T>::max() / 2 - 1000;
}
template <typename T>
constexpr typename std::enable_if<std::is_floating_point<T>::value, T>::type
inf_sub() {
return std::min(std::numeric_limits<T>::max() / 2 - 1000, T(1e50));
}
} // namespace sub
/// @return Returns a large finite value representable by the numeric type T.
/// @note It is guaranteed that the return values is strictly less than std::numeric_limits<T>::max() / 2.
template <typename T> constexpr T inf() {
static_assert(std::is_arithmetic<T>::value, "T must be arithmetic value");
return sub::inf_sub<T>();
}
using Cost = ll;
using Node = int;
struct Edge{
Cost cost; Node to;
Edge(Cost cost,Node to)
:cost(cost),to(to){}
};
ostream& operator << (ostream& os, Edge& e) {
cout << "(" << e.cost << "," << e.to << ") "; return os;
}
using Graph = vector<vector<Edge>>;
vector<Cost> dijkstra
(Graph &graph, Node start, Cost zero = 0LL)
{
using Pcn = pair<Cost,Node>;
priority_queue<Pcn,vector<Pcn>,greater<Pcn>> que;
vector<Cost> dist(graph.size(),inf<Cost>());
dist[start] = zero;
que.push(Pcn(zero,start));
while(!que.empty()){
Pcn p = que.top(); que.pop();
Node v = p.second; //
if(dist[v] < p.first) continue;
for(Edge e : graph[v]){
if(dist[v]+e.cost < dist[e.to]){
dist[e.to] = dist[v]+e.cost;
que.push(Pcn(dist[e.to],e.to));
}
}
}
return dist;
}
vector<Cost> dijkstra2
(Graph &graph,vector<Cost> &dist0, Node start, Cost zero = 0LL)
{
using Pcn = pair<Cost,Node>;
priority_queue<Pcn,vector<Pcn>,greater<Pcn>> que;
vector<Cost> dist(graph.size(),inf<Cost>());
int N = graph.size();
dist[0] = 0;
rep(i,N) for(auto&& e:graph[i]){
que.push(Pcn(dist0[i],e.to));
chmin(dist[e.to],dist0[i]);
}
while(!que.empty()){
Pcn p = que.top(); que.pop();
Node v = p.second; //
dump(v,p.first);
if(dist[v] < p.first) continue;
dump(v,p.first);
for(Edge e : graph[v]){
if(dist[v]+e.cost < dist[e.to]){
dist[e.to] = dist[v]+e.cost;
que.push(Pcn(dist[e.to],e.to));
}
}
}
dump(dist);
return dist;
}
void add_edge(Graph& g,int u,int v,ll c){
g[u].pb(Edge(c,v));
g[v].pb(Edge(c,u));
}
void _main(){
int N;
cin >> N ;
int M; cin >> M;
Graph g(N);
rep(i,M){
int u,v; ll c; cin >> u >> v >> c ;
u--; v--;
add_edge(g,u,v,c);
}
dump(g);
auto dist = dijkstra(g,0);
dump(dist);
auto dist2 = dijkstra2(g,dist,0);
rep(i,N) cout << dist[i] + dist2[i] << endl;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0