結果

問題 No.807 umg tours
ユーザー YDK1727YDK1727
提出日時 2019-05-01 18:30:47
言語 C++14
(gcc 12.3.0 + boost 1.83.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 5 ms
7,296 KB
testcase_01 AC 4 ms
7,296 KB
testcase_02 AC 5 ms
7,296 KB
testcase_03 AC 5 ms
7,296 KB
testcase_04 AC 4 ms
7,296 KB
testcase_05 AC 4 ms
7,296 KB
testcase_06 AC 5 ms
7,424 KB
testcase_07 AC 5 ms
7,296 KB
testcase_08 AC 5 ms
7,424 KB
testcase_09 AC 5 ms
7,296 KB
testcase_10 AC 5 ms
7,552 KB
testcase_11 AC 121 ms
17,880 KB
testcase_12 AC 105 ms
14,696 KB
testcase_13 AC 147 ms
17,520 KB
testcase_14 AC 57 ms
11,668 KB
testcase_15 AC 45 ms
10,496 KB
testcase_16 AC 157 ms
18,176 KB
testcase_17 AC 213 ms
21,060 KB
testcase_18 AC 221 ms
21,100 KB
testcase_19 AC 211 ms
19,344 KB
testcase_20 AC 101 ms
12,544 KB
testcase_21 AC 100 ms
12,672 KB
testcase_22 AC 38 ms
9,644 KB
testcase_23 AC 28 ms
9,216 KB
testcase_24 AC 91 ms
16,536 KB
testcase_25 AC 217 ms
20,900 KB
権限があれば一括ダウンロードができます

ソースコード

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