結果

問題 No.1364 [Renaming] Road to Cherry from Zelkova
コンテスト
ユーザー leaf_1415
提出日時 2021-01-22 21:54:46
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 178 ms / 2,500 ms
コード長 4,061 bytes
コンパイル時間 1,557 ms
コンパイル使用メモリ 96,020 KB
実行使用メモリ 33,028 KB
最終ジャッジ日時 2024-12-29 09:04:20
合計ジャッジ時間 7,350 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 45
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <cassert>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <string>
#include <algorithm>
#include <utility>
#include <complex>
#define rep(x, s, t) for(llint (x) = (s); (x) <= (t); (x)++)
#define chmin(x, y) (x) = min((x), (y))
#define chmax(x, y) (x) = max((x), (y))
#define all(x) (x).begin(),(x).end()
#define inf 1e18
#define mod 1000000007

using namespace std;

typedef long long llint;
typedef long long ll;
typedef pair<llint, llint> P;


struct SCC{
	int n;
	vector<vector<int> > G, revG, compG;
	vector<int> used, scc, topo;
	int sccid, sccnum;
	
	void tpdfs(int v)
	{
		used[v] = 1;
		for(int i = 0; i < G[v].size(); i++){
			if(!used[G[v][i]]) tpdfs(G[v][i]);
		}
		topo.push_back(v);
	}
	void sccdfs(int v, int id)
	{
		used[v] = 1;
		scc[v] = id;
		for(int i = 0; i < revG[v].size(); i++){
			if(!used[revG[v][i]]) sccdfs(revG[v][i], id);
		}
	}
	
	SCC(){}
	SCC(int n){  //V(G) = {1, 2, ..., n}, nを制約より大きくするときは注意
		this->n = n;
		G.resize(n+1);
		revG.resize(n+1);
		used.resize(n+1);
	}
	void init(){
		for(int i = 1; i <= n; i++){
			G[i].clear(), revG[i].clear();
			used[i] = 0;
		}
		topo.clear();
	}
	void add_edge(int u, int v)
	{
		G[u].push_back(v);
	}
	void tpsort()
	{
		topo.clear();
		for(int i = 1; i <= n; i++) used[i] = 0;
		for(int i = 1; i <= n; i++) if(!used[i]) tpdfs(i);
		reverse(topo.begin(), topo.end());
	}
	bool checkDAG(){ //先にtpsort()を呼ぶべし。DAGならtrueを返す
		for(int i = 1; i <= n; i++) used[i] = 0;
		for(int i = 0; i < topo.size(); i++){
			int v = topo[i];
			used[v] = 1;
			for(int j = 0; j < G[v].size(); j++){
				if(used[G[v][j]]) return false;
			}
		}
		return true;
	}
	int calcSCC(){  //先にtpsort()を呼ぶべし。戻り値はSCCの個数。SCC-IDは1-indexed
		scc.resize(n+1);
		for(int i = 1; i <= n; i++) revG[i].clear();
		for(int i = 1; i <= n; i++){
			for(int j = 0; j < G[i].size(); j++){
				revG[G[i][j]].push_back(i);
			}
		}
		sccid = 1;
		for(int i = 1; i <= n; i++) used[i] = 0;
		for(int i = 0; i < topo.size(); i++) if(!used[topo[i]]) sccdfs(topo[i], sccid++);
		return sccnum = sccid-1;
	}
	void compressSCC(bool simple = false){ //先にcalcSCC()を呼ぶべし。圧縮後のグラフはscc::compG
		compG.resize(sccnum+1);
		for(int i = 1; i <= n; i++){
			for(int j = 0; j < G[i].size(); j++){
				int u = G[i][j];
				if(scc[i] != scc[u]) compG[scc[i]].push_back(scc[u]);
			}
		}
		if(simple){
			for(int i = 1; i <= sccnum; i++){
				sort(compG[i].begin(), compG[i].end());
				compG[i].erase(unique(compG[i].begin(), compG[i].end()), compG[i].end());
			}
		}
	}
	
};

struct edge{
	ll to, cost, num;
	edge(){}
	edge(ll a, ll b, ll c){
		to = a, cost = b, num = c;
	}
};

ll n, m;
vector<edge> G[200005], revG[200005];
bool reachS[200005], reachT[200005], used[200005];
ll dpnum[200005], dpsum[200005];

void dfs(vector<edge> G[], ll v, bool reach[])
{
	reach[v] = true;
	for(auto e : G[v]){
		if(reach[e.to]) continue;
		dfs(G, e.to, reach);
	}
}

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> m;
	ll S = n+1, T = n;
	n++;
	
	ll u, v, l, a;
	rep(i, 1, m){
		cin >> u >> v >> l >> a;
		if(u == 0) u = S;
		if(v == 0) v = S;
		G[u].push_back(edge(v, l, a));
		revG[v].push_back(edge(u, l, a));
	}
	dfs(G, S, reachS);
	dfs(revG, T, reachT);
	
	rep(i, 1, n) used[i] = !reachS[i] || !reachT[i];
	
	SCC scc(n);
	rep(i, 1, n){
		if(used[i]) continue;
		for(auto e : G[i]){
			if(used[e.to]) continue;
			scc.add_edge(i, e.to);
		}
	}
	scc.tpsort();
	
	if(!scc.checkDAG()){
		cout << "INF" << endl;
		return 0;
	}
	
	dpnum[S] = 1, dpsum[S] = 0;
	for(auto v : scc.topo){
		if(used[v]) continue;
		for(auto e : G[v]){
			ll u = e.to, l = e.cost, a = e.num;
			(dpnum[u] += dpnum[v] * a % mod) %= mod;
			(dpsum[u] += (dpsum[v]+dpnum[v]*l%mod)%mod * a % mod) %= mod;
		}
	}
	cout << dpsum[T] << endl;
	
	return 0;
}
0