結果
問題 | No.1364 [Renaming] Road to Cherry from Zelkova |
ユーザー |
|
提出日時 | 2021-01-22 23:08:11 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,507 bytes |
コンパイル時間 | 1,942 ms |
コンパイル使用メモリ | 176,760 KB |
実行使用メモリ | 12,672 KB |
最終ジャッジ日時 | 2024-12-29 10:43:24 |
合計ジャッジ時間 | 7,512 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 44 WA * 1 |
ソースコード
// #include <bits/stdc++.h> using namespace std; #define fi first #define se second #define all(x) x.begin(), x.end() #define lch (o << 1) #define rch (o << 1 | 1) typedef double db; typedef long long ll; typedef unsigned int ui; typedef pair<int, int> pint; typedef tuple<int, int, int> tint; const int N = 1e5 + 5; const int MOD = 1e9 + 7; const int INF = 0x3f3f3f3f; const ll INF_LL = 0x3f3f3f3f3f3f3f3f; struct Adj { int v, w, s; }; int ind[N]; vector<Adj> a[N]; bool ok[N]; void dfs(int u) { ok[u] = 1; for (auto e: a[u]) { if (ok[e.v]) continue; dfs(e.v); } } ll sumLS[N], sumS[N]; int main() { ios::sync_with_stdio(0); int n, m; cin >> n >> m; for (int i = 1; i <= m; i++) { int u, v, w, s; cin >> u >> v >> w >> s; a[u].push_back((Adj){v, w, s}); } dfs(0); for (int u = 0; u <= n; u++) { if (!ok[u]) continue; for (auto e: a[u]) ind[e.v]++; } if (ind[0] > 0) { cout << "INF" << endl; return 0; } // topo queue<int> q; q.push(0); sumS[0] = 1; while (!q.empty()) { int u = q.front(); q.pop(); for (auto e: a[u]) { ind[e.v]--; if (ind[e.v] == 0) q.push(e.v); // cal sumLS[e.v] = (sumLS[e.v] + sumLS[u] * e.s + sumS[u] * e.w % MOD * e.s) % MOD; sumS[e.v] = (sumS[e.v] + sumS[u] * e.s) % MOD; } } bool flag = 0; for (int i = 0; i <= n; i++) if (ok[i] && ind[i]) flag = 1; if (flag) { cout << "INF" << endl; return 0; } ll ans = sumLS[n]; ans = (ans % MOD + MOD) % MOD; cout << ans << endl; return 0; }