結果
問題 | No.1364 [Renaming] Road to Cherry from Zelkova |
ユーザー |
![]() |
提出日時 | 2021-01-22 23:12:59 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 420 ms / 2,500 ms |
コード長 | 2,952 bytes |
コンパイル時間 | 1,569 ms |
コンパイル使用メモリ | 142,340 KB |
最終ジャッジ日時 | 2025-01-18 05:50:58 |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 45 |
ソースコード
#include <cstdio>#include <cstring>#include <iostream>#include <string>#include <cmath>#include <bitset>#include <vector>#include <map>#include <set>#include <queue>#include <deque>#include <algorithm>#include <complex>#include <unordered_map>#include <unordered_set>#include <random>#include <cassert>#include <fstream>#include <utility>#include <functional>#include <stack>#include <array>#include <list>#define popcount __builtin_popcountusing namespace std;typedef long long int ll;typedef pair<int, int> P;const ll MOD=1e9+7;struct SCC{vector<vector<int>> g, gr;int n, k;vector<int> cmp, vs;vector<bool> used;void dfs(int x){used[x]=1;for(auto y:g[x]){if(!used[y]) dfs(y);}vs.push_back(x);}void rdfs(int v, int k){used[v]=1;cmp[v]=k;for(auto y:gr[v]){if(!used[y]) rdfs(y, k);}}SCC(const vector<vector<int>> &g):g(g), n(g.size()), cmp(n), used(n){gr.resize(n);for(int x=0; x<n; x++) for(auto y:g[x]) gr[y].push_back(x);for(int i=0; i<n; i++){if(!used[i]) dfs(i);}fill(used.begin(), used.end(), 0);k=0;for(int i=vs.size()-1; i>=0; i--){if(!used[vs[i]]) rdfs(vs[i], k++);}}};int u[200010], v[200010];ll l[200020], a[200020];vector<P> g[200020];int main(){int n, m;cin>>n>>m;vector<vector<int>> g0(n+1);for(int i=0; i<m; i++){cin>>u[i]>>v[i]>>l[i]>>a[i];g[u[i]].push_back({v[i], i});g0[u[i]].push_back(v[i]);}SCC scc(g0);vector<vector<int>> w(scc.k);for(int i=0; i<=n; i++){w[scc.cmp[i]].push_back(i);}bool dame[100010]={};for(int i=0; i<scc.k; i++){if(w[i].size()>1){for(auto x:w[i]) dame[x]=1;}}bool used[100010]={};used[0]=1;queue<int> que;que.push(0);while(!que.empty()){int x=que.front(); que.pop();for(auto q:g[x]){int y=q.first;if(!used[y]){que.push(y);used[y]=1;}}}if(!used[n]){cout<<0<<endl;return 0;}if(dame[0] || dame[n]){cout<<"INF"<<endl;return 0;}ll dp[100010]={};dp[0]=1;ll dps[100010]={};bool ok[100010]={}; ok[0]=1;for(int i=0; i<scc.k; i++){if(w[i].size()>1) continue;int x=w[i][0];if(!ok[x]) continue;for(auto q:g[x]){int i=q.second;int y=q.first;if(dame[y]){continue;}ok[y]=1;(dp[y]+=dp[x]*a[i])%=MOD;(dps[y]+=dps[x]*a[i]+dp[x]*l[i]%MOD*a[i])%=MOD;}}if(!ok[n]){cout<<"INF"<<endl;}else{cout<<dps[n]<<endl;}return 0;}