結果

問題 No.807 umg tours
ユーザー YDK1727YDK1727
提出日時 2019-05-01 18:17:44
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 379 ms / 4,000 ms
コード長 1,747 bytes
コンパイル時間 1,770 ms
コンパイル使用メモリ 176,000 KB
実行使用メモリ 22,444 KB
最終ジャッジ日時 2024-05-02 23:51:24
合計ジャッジ時間 6,808 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
7,364 KB
testcase_01 AC 5 ms
7,296 KB
testcase_02 AC 5 ms
7,424 KB
testcase_03 AC 4 ms
7,240 KB
testcase_04 AC 4 ms
7,368 KB
testcase_05 AC 4 ms
7,264 KB
testcase_06 AC 4 ms
7,360 KB
testcase_07 AC 4 ms
7,368 KB
testcase_08 AC 4 ms
7,360 KB
testcase_09 AC 4 ms
7,240 KB
testcase_10 AC 4 ms
7,304 KB
testcase_11 AC 239 ms
18,008 KB
testcase_12 AC 197 ms
14,792 KB
testcase_13 AC 290 ms
17,628 KB
testcase_14 AC 110 ms
11,896 KB
testcase_15 AC 87 ms
10,564 KB
testcase_16 AC 295 ms
18,284 KB
testcase_17 AC 379 ms
22,444 KB
testcase_18 AC 370 ms
21,988 KB
testcase_19 AC 370 ms
19,316 KB
testcase_20 AC 180 ms
12,608 KB
testcase_21 AC 188 ms
12,864 KB
testcase_22 AC 73 ms
9,728 KB
testcase_23 AC 54 ms
9,412 KB
testcase_24 AC 172 ms
16,388 KB
testcase_25 AC 377 ms
22,168 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()
{
  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