#1179441 (C++23) No.3669 误差绝不允许

• 問題: No.3669 误差绝不允许
• ユーザー: TKTYI
• 提出日時: 2026-08-27 11:45:56
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0)
• 結果: AC
• 実行時間: 777 ms / 3,000 ms
• コード長: 4,702 bytes
• コンパイル時間: 2,880 ms
• コンパイル使用メモリ: 361,900 KB
• 実行使用メモリ: 22,908 KB
• 最終ジャッジ日時: 2026-09-04 22:55:10
• 合計ジャッジ時間: 19,236 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge4_0

ファイルパターン	結果
sample	AC * 2
other	AC * 30

ソースコード

#include <bits/stdc++.h>
using namespace std;
struct bigint {
  vector<int> d;
  bigint(int x) {
    while (x) {
      d.emplace_back(x % 1000000000);
      x /= 1000000000;
    }
  }
  bigint () : d(0) {}
  bool operator < (const bigint& n) const {
    if (n.d.size() != d.size()) return d.size() < n.d.size();
    int i = int(d.size()) - 1;
    while (i >= 0) {
      if (n.d[i] != d[i]) return d[i] < n.d[i];
      i--;
    }
    return false;
  }
  bool operator <= (const bigint& n) const {
    if (n.d.size() != d.size()) return d.size() < n.d.size();
    int i = int(d.size()) - 1;
    while (i >= 0) {
      if (n.d[i] != d[i]) return d[i] < n.d[i];
      i--;
    }
    return true;
  }
  bool operator > (const bigint& n) const {
    if (n.d.size() != d.size()) return d.size() > n.d.size();
    int i = int(d.size()) - 1;
    while (i >= 0) {
      if (n.d[i] != d[i]) return d[i] > n.d[i];
      i--;
    }
    return false;
  }
  bool operator >= (const bigint& n) const {
    if (n.d.size() != d.size()) return d.size() > n.d.size();
    int i = int(d.size()) - 1;
    while (i >= 0) {
      if (n.d[i] != d[i]) return d[i] > n.d[i];
      i--;
    }
    return true;
  }
  bool operator == (const bigint& n) const {
    return d == n.d;
  }
  bool operator != (const bigint& n) const {
    return d != n.d;
  }
  bigint operator + (const bigint& n) const {
    auto res = *this;
    if (n.d.size() > res.d.size()) res.d.resize(n.d.size());
    for (int i = 0; i < n.d.size(); i++) res.d[i] += n.d[i];
    for (int i = 0; i < res.d.size(); i++) if (res.d[i] >= 1000000000) {
      if (i + 1 == res.d.size()) res.d.emplace_back(0);
      res.d[i + 1] ++;
      res.d[i] -= 1000000000;
    }
    return res;
  }
  bigint operator - (const bigint& n) const {
    bigint res = *this;
    assert(n <= res);
    for (int i = 0; i < n.d.size(); i++) res.d[i] -= n.d[i];
    for (int i = 0; i < res.d.size(); i++) if (res.d[i] < 0) {
      res.d[i + 1] --;
      res.d[i] += 1000000000;
    }
    while((!res.d.empty()) && res.d.back() == 0) res.d.erase(res.d.end() - 1);
    return res;
  }
  bigint operator * (const int& n) const {
    if (d.empty() || !n) return 0;
    bigint res = *this;
    long long x = 0;
    for (int i = 0; i < res.d.size(); i++) {
      x += 1ll * n * res.d[i];
      res.d[i] = x % 1000000000;
      x /= 1000000000;
    }
    if (x) res.d.emplace_back(x);
    return res;
  }
  int operator % (const int& n) const {
    assert(n);
    long long r = 0;
    for (int i = d.size() - 1; i >= 0; i--) {
      r = 1000000000 * r + d[i];
      r %= n;
    }
    return r;
  }
  bigint operator / (const int& n) const {
    assert(n);
    bigint q = 0;
    long long r = 0;
    for (int i = d.size() - 1; i >= 0; i--) {
      r = 1000000000 * r + d[i];
      if (r >= n || !q.d.empty()) {
        q.d.insert(q.d.begin(), r / n);
      }
      r %= n;
    }
    return q;
  }
};
bigint mygcd(bigint a, int b) {
  return __gcd(a % b, b);
}
template<typename T>
using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
int main() {
  int N, M;
  cin >> N >> M;
  vector<bool> prime(300, 1);
  prime[0] = prime[1] = 0;
  for (int i = 2; i < 300; i++) if (prime[i]) {
    for (int j = 2 * i; j < 300; j += i) prime[j]=0;
  }
  vector<int> e(300);
  bigint LCM = 1;
  for (int i = 2; i < 300; i++) if (prime[i]) {
    int n = 300;
    while (n >= i) e[i]++, n /= i, LCM = LCM * i;
  }
  vector<vector<pair<int, bigint>>> E(N);
  cerr << clock() << "ms" << endl;
  while (M--) {
    int u, v, a, b;
    cin >> u >> v >> a >> b;
    u--; v--;
    E[u].emplace_back(v, LCM / b * a);
    E[v].emplace_back(u, LCM / b * a);
  }
  cerr << clock() << "ms" << endl;
  vector<bigint> D(N, LCM * 300 * N);
  D[0] = 0;
  min_priority_queue<pair<bigint, int>> Q;
  Q.emplace(D[0], 0);
  while (!Q.empty()) {
    auto[d, v] = Q.top(); Q.pop();
    if (d != D[v]) continue;
    for (auto[u, w] : E[v]) {
      auto _d = d + w;
      if (_d < D[u]) {
        D[u] = _d;
        Q.emplace(_d, u);
      }
    }
  }
  cerr << clock() << "ms" << endl;
  for (int i = 1; i < N; i++) {
    auto a = D[i], b = LCM;
    for (int j = 2; j < 300; j++) {
      for (int k = 0; k < e[j]; k++) {
        if(a % j) break;
        a = a / j; b = b / j;
      }
    }
    for (int j = a.d.size() - 1; j >= 0; j--) {
        auto S = to_string(a.d[j]);
        if (j != a.d.size() - 1) S = string(9 - S.size(), '0') + S;
        cout << S;
    }
    cout << " ";
    for (int j = b.d.size() - 1; j >= 0; j--) {
        auto S = to_string(b.d[j]);
        if (j != b.d.size() - 1) S = string(9 - S.size(), '0') + S;
        cout << S;
    }
    cout << '\n';
  }
  cerr << clock() << "ms" << endl;
}