結果

問題 No.1364 [Renaming] Road to Cherry from Zelkova
ユーザー kappybarkappybar
提出日時 2021-01-22 22:35:24
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 4,006 bytes
コンパイル時間 2,543 ms
コンパイル使用メモリ 188,744 KB
実行使用メモリ 40,320 KB
最終ジャッジ日時 2024-12-29 09:09:13
合計ジャッジ時間 14,685 ms
ジャッジサーバーID
(参考情報)
judge1 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 44 WA * 1
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define chmin(x,y) x = min((x),(y));
#define chmax(x,y) x = max((x),(y));
using namespace std;
using ll = long long ;
using P = pair<int,int> ;
using pll = pair<long long,long long>;
const int INF = 1e9;
const long long LINF = 1e17;
const int MOD = 1000000007;
//const int MOD = 998244353;
const double PI = 3.14159265358979323846;
template<int mod> struct ModInt{
long long x=0;
constexpr ModInt(long long x=0):x((x%mod+mod)%mod){}
constexpr ModInt operator+(const ModInt& r)const{return ModInt(*this)+=r;}
constexpr ModInt operator-(const ModInt& r)const{return ModInt(*this)-=r;}
constexpr ModInt operator*(const ModInt& r)const{return ModInt(*this)*=r;}
constexpr ModInt operator/(const ModInt& r)const{return ModInt(*this)/=r;}
constexpr ModInt& operator+=(const ModInt& r){ if((x+=r.x)>=mod) x-=mod; return *this;}
constexpr ModInt& operator-=(const ModInt& r){ if((x-=r.x)<0) x+=mod; return *this;}
constexpr ModInt& operator*=(const ModInt& r){ if((x*=r.x)>=mod) x%=mod; return *this;}
constexpr ModInt& operator/=(const ModInt& r){ return *this*=r.inv();}
ModInt inv() const {
long long s=x,sx=1,sy=0,t=mod,tx=0,ty=1;
while(s%t!=0){
long long temp=s/t,u=s-t*temp,ux=sx-temp*tx,uy=sy-temp*ty;
s=t;sx=tx;sy=ty;
t=u;tx=ux;ty=uy;
}
return ModInt(tx);
}
ModInt pow(long long n) const {
ModInt a=1;
ModInt b=*this;
while(n>0){
if(n&1) a*=b;
b*=b;
n>>=1;
}
return a;
}
friend constexpr ostream& operator<<(ostream& os,const ModInt<mod>& a) {return os << a.x;}
friend constexpr istream& operator>>(istream& is,ModInt<mod>& a) {return is >> a.x;}
};
using mint = ModInt<MOD>;
vector<int> ToplogicalSort(vector<vector<int>> &G,vector<int> &Indegree){
int n = (int)G.size();
vector<int> res(n);
queue<int> q;
for(int i=0;i<n;i++){
if(Indegree[i] == 0){
q.push(i);
}
}
int i = 0;
while(!q.empty()){
int now = q.front();
res[i++] = now;
q.pop();
for(int v:G[now]){
--Indegree[v];
if(Indegree[v] == 0) q.push(v);
}
}
if(i==n) return res;
else return {-1};
}
struct edge{
ll to;
ll l,a;
};
mint dp[100005];
mint cnt[100005];
int seen[100005];
int main(){
int n,m;
cin >> n >> m;
vector<vector<int>> G(n+1);
vector<vector<edge>> graph(n+1);
vector<int> Indegree(n+1,0);
rep(i,m){
ll u,v,l,a;
cin >> u >> v >> l >> a;
G[u].push_back(v);
graph[u].push_back(edge{v,l,a});
Indegree[v]++;
}
int n_ = 0;
map<int,int> temp_real;
map<int,int> real_temp;
auto dfs = [&](auto&& dfs,int i) -> void{
if(seen[i]==1) return;
seen[i] = 1;
temp_real[n_] = i;
real_temp[i] = n_;
++n_;
for(int j:G[i]){
if(seen[j]) continue;
dfs(dfs,j);
}
};
dfs(dfs,0);
vector<int> Indegree_(n_,0);
vector<vector<int>> G_(n_);
rep(i,n+1){
if(real_temp.count(i) == 0) continue;
int idx = real_temp[i];
for(int j:G[i]){
if(real_temp.count(j) > 0){
G_[idx].push_back(real_temp[j]);
Indegree_[real_temp[j]] ++;
}
}
}
if(real_temp.count(n) == 0){
cout << 0 << endl;
return 0;
}
vector<int> top = ToplogicalSort(G_,Indegree_);
if(top[0]==-1){
cout << "INF" << endl;
return 0;
}
vector<int> topo(n_);
rep(i,n_){
topo[i] = temp_real[top[i]];
}
dp[0] = 0;
cnt[0] = 1;
for(int i:topo){
for(auto e:graph[i]){
dp[e.to] += dp[i] * e.a + cnt[i] * e.a * e.l;
cnt[e.to] += cnt[i] * e.a;
}
}
cout << dp[n] << endl;
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0