結果

問題 No.807 umg tours
コンテスト
ユーザー YDK1727
提出日時 2019-05-01 18:30:47
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 221 ms / 4,000 ms
コード長 1,769 bytes
コンパイル時間 2,085 ms
コンパイル使用メモリ 176,296 KB
実行使用メモリ 21,100 KB
最終ジャッジ日時 2024-11-23 19:29:21
合計ジャッジ時間 5,186 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include "bits/stdc++.h"
#define ALL(x) x.begin(), x.end()
#define LEN(x) (int)x.size()
#define iostreamBooster() do{ cin.tie(nullptr); ios_base::sync_with_stdio(false); }while(0)
using namespace std;
typedef int64_t i64;
typedef pair<i64,int> pii;
template<class A, class B>inline bool chmax(A &a, const B &b){return b>a ? a=b,1 : 0;}
template<class A, class B>inline bool chmin(A &a, const B &b){return b<a ? a=b,1 : 0;}
constexpr int INF = 0x3f3f3f3f;
constexpr i64 LINF = 0x3f3f3f3f'3f3f3f3f;

struct P {
  i64 c;
  int to;
  bool used;

  P(i64 c=0, int to=0, bool used=false): c(c), to(to), used(used) {};
  bool operator< (const P &that) const { return this->c < that.c; }
  bool operator> (const P &that) const { return this->c > that.c; }
};

int N, M;
vector<pii> G[100010];

// dist[node][ticket-used]
i64 dist[100010][2];

void dijkstra(int s)
{
  priority_queue<P, vector<P>, greater<P>> pq;
  memset(dist, 0x3f, sizeof(dist));

  pq.emplace(0, s, false);
  dist[s][false] = 0;
  dist[s][true] = 0;

  while( !pq.empty() ) {
    const auto now = move(pq.top()); pq.pop();
    if (dist[now.to][now.used] < now.c) continue;

    for (const auto &e : G[now.to]) {
      const int nxt = e.second;
      const i64 ncost = e.first + now.c;

      if (chmin(dist[nxt][now.used], ncost))
        pq.emplace(ncost, nxt, now.used);

      if (!now.used && chmin(dist[nxt][true], now.c))
          pq.emplace(now.c, nxt, true);
    }
  }
}

signed main()
{
  iostreamBooster();

  cin >> N >> M;

  for (int i = 0; i < M; ++i) {
    int s, t, c;
    cin >> s >>t >> c;
    --s, --t;
    G[s].emplace_back(c, t);
    G[t].emplace_back(c, s);
  }

  dijkstra(0);

  for (int i = 0; i < N; ++i) {
    cout << dist[i][false] + dist[i][true] << '\n';
  }


  return 0;
}
0