結果

問題 No.3669 误差绝不允许
コンテスト
ユーザー tnakao0123
提出日時 2026-09-05 19:34:13
言語 C++17
(gcc 15.3.0 + boost 1.92.0)
コンパイル:
g++-15 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
WA  
実行時間 -
コード長 1,740 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 426 ms
コンパイル使用メモリ 80,464 KB
実行使用メモリ 10,012 KB
最終ジャッジ日時 2026-09-05 19:34:25
合計ジャッジ時間 8,198 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge1_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 10 WA * 2 TLE * 1 -- * 17
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

/* -*- coding: utf-8 -*-
 *
 * 3669.cc:  No.3669 隸ｯ蟾ｮ扈昜ｸ榊・隶ｸ - yukicoder
 */

#include<cstdio>
#include<vector>
#include<queue>
#include<algorithm>
#include<numeric>
#include<utility>

using namespace std;

/* constant */

const int MAX_N = 30000;
const int MAX_A = 300;
const int INF = MAX_N * MAX_A + 1;

/* typedef */

using ll = long long;

struct Frac {
  ll n, d;
  Frac(int _n = 0, int _d = 1): n(_n), d(_d) { __reduce(); }

  void __reduce() {
    int g = gcd(abs(n), d);
    n /= g, d /= g;
  }

  Frac operator+(const Frac &f) { return Frac(n * f.d + f.n * d, d * f.d); }
  Frac operator-() { return Frac(-n, d); }

  bool operator<(const Frac &f) const { return n * f.d < f.n * d; }
  bool operator>(const Frac &f) const { return n * f.d > f.n * d; }
  bool operator==(const Frac &f) const { return n * f.d == f.n * d; }
  bool operator!=(const Frac &f) const { return n * f.d != f.n * d; }
};

using pif = pair<int,Frac>;
using pfi = pair<Frac,int>;
using vpif = vector<pif>;

/* global variables */

vpif nbrs[MAX_N];
Frac ds[MAX_N];

/* subroutines */

/* main */

int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 0; i < m; i++) {
    int u, v, a, b;
    scanf("%d%d%d%d", &u, &v, &a, &b);
    u--, v--;
    Frac w(a, b);
    nbrs[u].push_back({v, w});
    nbrs[v].push_back({u, w});
  }

  fill(ds, ds + n, INF);
  ds[0] = 0;

  priority_queue<pfi> q;
  q.push({0, 0});

  while (! q.empty()) {
    auto [ud, u] = q.top(); q.pop();
    ud = -ud;
    if (ds[u] != ud) continue;

    for (auto [v, w]: nbrs[u]) {
      auto vd = ud + w;
      if (ds[v] > vd) ds[v] = vd, q.push({-vd, v});
    }
  }

  for (int i = 1; i < n; i++) printf("%lld %lld\n", ds[i].n, ds[i].d);
  
  return 0;
}
0