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

• 問題: No.3669 误差绝不允许
• ユーザー: TKTYI
• 提出日時: 2026-08-27 11:08:24
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0)
• 結果: TLE
• 実行時間: -
• コード長: 5,523 bytes
• コンパイル時間: 3,211 ms
• コンパイル使用メモリ: 364,392 KB
• 実行使用メモリ: 6,400 KB
• 最終ジャッジ日時: 2026-09-04 22:54:50
• 合計ジャッジ時間: 8,307 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge4_1

ファイルパターン	結果
sample	AC * 2
other	AC * 9 TLE * 1 -- * 20

ソースコード

#include <bits/stdc++.h>
using namespace std;
struct bigint {
  vector<long long> d;
  bigint(long long x) {
    while (x) {
      d.emplace_back(x % 1000000);
      x /= 1000000;
    }
  }
  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] >= 1000000) {
      if (i + 1 == res.d.size()) res.d.emplace_back(0);
      res.d[i + 1] ++;
      res.d[i] -= 1000000;
    }
    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] += 1000000;
    }
    while((!res.d.empty()) && res.d.back() == 0) res.d.erase(res.d.end() - 1);
    return res;
  }
  bigint operator * (const bigint& n) const {
    bigint res;
    if (d.empty() || n.d.empty()) return res;
    res.d.resize(d.size() + n.d.size() - 1);
    for (int i = 0; i < d.size(); i++) {
      for (int j = 0; j < n.d.size(); j++) {
        res.d[i + j] += d[i] * n.d[j];
      }
    }
    for (int i = 0; i < res.d.size(); i++) if(res.d[i] >= 1000000) {
      if (i + 1 == res.d.size()) res.d.emplace_back(0);
      res.d[i + 1] += res.d[i] / 1000000;
      res.d[i] %= 1000000;
    }
    return res;
  }
  bigint operator % (const bigint& n) const {
    assert(!n.d.empty());
    bigint r;
    for (int i = d.size() - 1; i >= 0; i--) {
      if (d[i] || !r.d.empty()) r.d.insert(r.d.begin(), d[i]);
      int L = 0, R = 1000000;
      while (R - L > 1) {
        int M = (L + R) / 2;
        if (bigint(M) * n <= r) L = M;
        else R = M;
      }
      r = r - bigint(L) * n;
    }
    return r;
  }
  bigint operator / (const bigint& n) const {
    assert(!n.d.empty());
    bigint q = 0, r = 0;
    for (int i = d.size() - 1; i >= 0; i--) {
      if (d[i] || !r.d.empty()) r.d.insert(r.d.begin(), d[i]);
      int L = 0, R = 1000000;
      while (R - L > 1) {
        int M = (L + R) / 2;
        if (bigint(M) * n <= r) L = M;
        else R = M;
      }
      if (L || !q.d.empty()) q.d.insert(q.d.begin(), L);
      r = r - bigint(L) * n;
    }
    return q;
  }
};
bigint mygcd(bigint a, bigint b) {
  while (!b.d.empty()) {
    a = a % b;
    swap(a, b);
  }
  return a;
}
struct rational {
  bigint a, b;
  rational(bigint _a, bigint _b) : a(_a), b(_b) {}
  bool operator < (const rational &r) const {
    return a * r.b < b * r.a;
  }
  bool operator <= (const rational& r) const {
    return a * r.b <= b * r.a; 
  }
  bool operator > (const rational& r) const {
    return a * r.b > b * r.a;
  }
  bool operator >= (const rational& r) const {
    return a * r.b >= b * r.a; 
  }
  bool operator == (const rational& r) const {
    return a * r.b == b * r.a; 
  }
  bool operator != (const rational& r) const {
    return a * r.b != b * r.a; 
  }
  rational operator + (const rational& r) const {
    return rational(a * r.b + b * r.a, b * r.b);
  }
};
template<typename T>
using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
int main() {
  int N, M;
  cin >> N >> M;
  vector<vector<pair<int, rational>>> E(N);
  while (M--) {
    int u, v, a, b;
    cin >> u >> v >> a >> b;
    u--; v--;
    E[u].emplace_back(v, rational(a, b));
    E[v].emplace_back(u, rational(a, b));
  }
  vector<rational> D(N, rational(300 * N, 1));
  D[0] = rational(0, 1);
  min_priority_queue<pair<rational, 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);
      }
    }
  }
  for (int i = 1; i < N; i++) {
    auto a = D[i].a, b = D[i].b;
    auto g = mygcd(a, b);
    a = a / g; b = b / g;
    for (int i = a.d.size() - 1; i >= 0; i--) {
        auto S = to_string(a.d[i]);
        if (i != a.d.size() - 1) S = string(6 - S.size(), '0') + S;
        cout << S;
    }
    cout << " ";
    for (int i = b.d.size() - 1; i >= 0; i--) {
        auto S = to_string(b.d[i]);
        if (i != b.d.size() - 1) S = string(6 - S.size(), '0') + S;
        cout << S;
    }
    cout << endl;
  }
  cerr << clock() << "ms" << endl;
}