結果
問題 | No.1364 [Renaming] Road to Cherry from Zelkova |
ユーザー |
|
提出日時 | 2021-01-21 23:47:30 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 575 ms / 2,500 ms |
コード長 | 3,716 bytes |
コンパイル時間 | 2,848 ms |
コンパイル使用メモリ | 80,460 KB |
実行使用メモリ | 114,908 KB |
最終ジャッジ日時 | 2024-12-29 09:02:59 |
合計ジャッジ時間 | 19,790 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 45 |
ソースコード
import java.io.IOException;import java.io.InputStream;import java.util.ArrayList;import java.util.Arrays;import java.util.NoSuchElementException;public class Main {public static void main(String[] args) {new Main().run();}final long p=(long)1e9+7;class Edge {int src, dst;long dist, cnt;public Edge(int src, int dst, long dist, long cnt) {this.src = src;this.dst = dst;this.dist = dist;this.cnt = cnt;}}void run() {FastScanner sc=new FastScanner();int N=sc.nextInt()+1;int M=sc.nextInt();ArrayList<Edge>[] g=new ArrayList[N];ArrayList<Edge>[] grev=new ArrayList[N];for (int i=0;i<g.length;++i) g[i]=new ArrayList<>();for (int i=0;i<g.length;++i) grev[i]=new ArrayList<>();for (int i=0;i<M;++i) {int u=sc.nextInt();int v=sc.nextInt();int l=sc.nextInt();int a=sc.nextInt();g[u].add(new Edge(u, v, l, a));grev[v].add(new Edge(v, u, l, a));}long[] ans=new long[N];long[] cnt=new long[N];cnt[N-1]=1;int[] state=new int[N];boolean[] a=new boolean[N];boolean[] b=new boolean[N];dfs0(0,g,a);dfs0(N-1,grev,b);for (int i=0;i<N;++i) a[i] &= b[i];Arrays.fill(state, 0);dfs(0, g, ans, state, cnt, a);System.out.println(ans[0]);}void dfs0(int cur, ArrayList<Edge>[] g, boolean[] valid) {valid[cur]=true;for (Edge e:g[cur]) {if (!valid[e.dst]) dfs0(e.dst,g,valid);}}void dfs(int cur, ArrayList<Edge>[] g, long[] ans, int[] state, long[] cnt, boolean[] ok) {state[cur]=1;for (Edge e:g[cur]) if (ok[e.dst]) {if (state[e.dst]==1) {System.out.println("INF");System.exit(0);}if (state[e.dst]==0) dfs(e.dst,g,ans,state,cnt,ok);}for (Edge e:g[cur]) if (ok[e.dst]){cnt[cur]+=cnt[e.dst]*e.cnt%p;cnt[cur]%=p;ans[cur]+=ans[e.dst]*e.cnt%p+cnt[e.dst]*e.cnt%p*e.dist%p;ans[cur]%=p;}state[cur]=2;}void tr(Object...objects) {System.out.println(Arrays.deepToString(objects));}}class FastScanner {private final InputStream in = System.in;private final byte[] buffer = new byte[1024];private int ptr = 0;private int buflen = 0;private boolean hasNextByte() {if (ptr < buflen) {return true;} else {ptr = 0;try {buflen = in.read(buffer);} catch (IOException e) {e.printStackTrace();}if (buflen <= 0) {return false;}}return true;}private int readByte() {if (hasNextByte())return buffer[ptr++];elsereturn -1;}private static boolean isPrintableChar(int c) {return 33 <= c && c <= 126;}public boolean hasNext() {while (hasNextByte() && !isPrintableChar(buffer[ptr]))ptr++;return hasNextByte();}public String next() {if (!hasNext())throw new NoSuchElementException();StringBuilder sb = new StringBuilder();int b = readByte();while (isPrintableChar(b)) {sb.appendCodePoint(b);b = readByte();}return sb.toString();}public long nextLong() {if (!hasNext())throw new NoSuchElementException();long n = 0;boolean minus = false;int b = readByte();if (b == '-') {minus = true;b = readByte();}if (b < '0' || '9' < b) {throw new NumberFormatException();}while (true) {if ('0' <= b && b <= '9') {n *= 10;n += b - '0';} else if (b == -1 || !isPrintableChar(b)) {return minus ? -n : n;} else {throw new NumberFormatException();}b = readByte();}}public int nextInt() {long nl = nextLong();if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE)throw new NumberFormatException();return (int) nl;}public double nextDouble() {return Double.parseDouble(next());}}