結果

問題 No.3669 误差绝不允许
コンテスト
ユーザー TKTYI
提出日時 2026-08-26 18:46:15
言語 C++23
(gcc 15.3.0 + boost 1.92.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
TLE  
実行時間 -
コード長 4,925 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,245 ms
コンパイル使用メモリ 361,876 KB
実行使用メモリ 22,436 KB
最終ジャッジ日時 2026-09-04 22:54:29
合計ジャッジ時間 9,252 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge4_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 10 TLE * 1 -- * 19
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
struct bigint {
  vector<short> d;
  bigint(int x) {
    while (x) {
      d.emplace_back(x % 10);
      x /= 10;
    }
  }
  bool operator < (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 <= (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 > (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 >= (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 == (bigint n) const {
    return d == n.d;
  }
  bool operator != (bigint n) const {
    return d != n.d;
  }
  bigint operator + (bigint n) const {
    if (n.d.size() < d.size()) n.d.resize(d.size());
    for (int i = 0; i < d.size(); i++) n.d[i] += d[i];
    for (int i = 0; i < n.d.size(); i++) if (n.d[i] >= 10) {
      if (i + 1 == n.d.size()) n.d.emplace_back(0);
      n.d[i + 1] ++;
      n.d[i] -= 10;
    }
    return n;
  }
  bigint operator - (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] += 10;
    }
    while((!res.d.empty()) && res.d.back() == 0) res.d.erase(res.d.end() - 1);
    return res;
  }
  bigint operator * (bigint n) const {
    bigint res(0);
    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] >= 10) {
      if (i + 1 == res.d.size()) res.d.emplace_back(0);
      res.d[i + 1] += res.d[i] / 10;
      res.d[i] %= 10;
    }
    return res;
  }
  bigint operator % (bigint n) const {
    assert(!n.d.empty());
    bigint r(0);
    for (int i = d.size() - 1; i >= 0; i--) {
      r = bigint(10) * r + d[i];
      int L = 0, R = 10;
      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 / (bigint n) const {
    assert(!n.d.empty());
    bigint q = 0, r = 0;
    for (int i = d.size() - 1; i >= 0; i--) {
      r = bigint(10) * r + d[i];
      q = bigint(10) * q;
      int L = 0, R = 10;
      while (R - L > 1) {
        int M = (L + R) / 2;
        if (bigint(M) * n <= r) L = M;
        else R = M;
      }
      q = q + L;
      r = r - bigint(L) * n;
    }
    return q;
  }
};
bigint mygcd(bigint a, bigint b) {
  while (!a.d.empty()) {
    swap(a, b);
    a = a % b;
  }
  return b;
}
struct rational {
  bigint a, b;
  rational(bigint _a, bigint _b) : a(_a / mygcd(_a, _b)), b(_b / mygcd(_a, _b)) {}
  bool operator < (rational r) const {
    return a * r.b < b * r.a;
  }
  bool operator <= (rational r) const {
    return a * r.b <= b * r.a; 
  }
  bool operator > (rational r) const {
    return a * r.b > b * r.a;
  }
  bool operator >= (rational r) const {
    return a * r.b >= b * r.a; 
  }
  bool operator == (rational r) const {
    return a * r.b == b * r.a; 
  }
  bool operator != (rational r) const {
    return a * r.b != b * r.a; 
  }
  rational operator + (rational r) const {
    bigint na = a * r.b + b * r.a;
    bigint nb = b * r.b;
    return rational(na, nb);
  }
};
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]) {
      if (d + w < D[u]) {
        D[u] = d + w;
        Q.emplace(D[u], u);
      }
    }
  }
  for (int i = 1; i < N; i++) {
    auto a = D[i].a.d, b = D[i].b.d;
    for (int i = a.size() - 1; i >= 0; i--) cout << a[i]; cout << " ";
    for (int i = b.size() - 1; i >= 0; i--) cout << b[i]; cout << endl;
  }
}
0