結果
問題 | No.2569 はじめてのおつかいHard |
ユーザー |
|
提出日時 | 2023-12-02 16:47:32 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 1,734 ms / 2,000 ms |
コード長 | 15,238 bytes |
コンパイル時間 | 5,235 ms |
コンパイル使用メモリ | 96,800 KB |
実行使用メモリ | 173,388 KB |
最終ジャッジ日時 | 2024-09-26 20:43:44 |
合計ジャッジ時間 | 16,916 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 10 |
ソースコード
import static java.lang.Math.*;import static java.util.Arrays.*;import java.io.*;import java.lang.reflect.Array;import java.math.*;import java.util.*;import java.util.concurrent.ThreadLocalRandom;import java.util.function.*;import java.util.stream.*;class Solver{long st = System.currentTimeMillis();long elapsed(){ return System.currentTimeMillis() -st; }void reset(){ st = System.currentTimeMillis(); }static int infI = (1 <<30) -1;static long infL = 1L <<60;//static long mod = (int) 1e9 +7;static long mod = 998244353;static String yes = "Yes";static String no = "No";static Random rd = ThreadLocalRandom.current();MyReader in = new MyReader(System.in);MyWriter out = new MyWriter(System.out);MyWriter log = new MyWriter(System.err){@Overridevoid println(Object obj){ super.println(obj == null ? "null" : obj); };@Overrideprotected void ln(){super.ln();flush();};};Object solve(){int N = in.it();int M = in.it();var go = new Dijkstra<Long,Long>(N,true){protected Long zero(){return 0l;}protected Long inf(){return infL;}protected Long f(Long l,Long val){return l+val;}};var bk = new Dijkstra<Long,Long>(N,true){protected Long zero(){return 0l;}protected Long inf(){return infL;}protected Long f(Long l,Long val){return l+val;}};while(M-->0){int u = in.idx();int v = in.idx();long t = in.lg();go.addEdge(u,v,t);bk.addEdge(v,u,t);}bk.calcFrom(N-2);long[] toN2= new long[N];for(int i=0;i<N;i++)toN2[i] = bk.len(i);bk.calcFrom(N-1);long[] toN1= new long[N];for(int i=0;i<N;i++)toN1[i] = bk.len(i);go.calcFrom(N-2);long[] fromN2= new long[N];for(int i=0;i<N;i++)fromN2[i] = go.len(i);go.calcFrom(N-1);long[] fromN1= new long[N];for(int i=0;i<N;i++)fromN1[i] = go.len(i);for(int k = 0 ;k<N-2;k++){long ans = infL;ans = min(ans,toN2[k]+fromN2[N-1]+fromN1[k]);ans = min(ans,toN1[k]+fromN1[N-2]+fromN2[k]);out.println(ans==infL?-1:ans);}return null;}long ceil(long a,long b){return (a+b-1)/b;}private long pow(long x,long n,long mod){long ret = 1;for (x %= mod;0 < n;x = x *x %mod,n >>= 1)if ((n &1) == 1)ret = ret *x %mod;return ret;}}abstract class Seg<V, F> {protected int n,log;private V[] val;private F[] lazy;private int[] l,r;@SuppressWarnings("unchecked")Seg(int n){this.n = n;while (1 <<log <= n)log++;val = (V[]) new Object[n <<1];lazy = (F[]) new Object[n];l = new int[n <<1];r = new int[n <<1];for (int i = -1;++i < n;l[i +n] = i,r[i +n] = i +1)val[i +n] = init(i);for (int i = n;--i > 0;l[i] = l[i <<1],r[i] = r[i <<1 |1])merge(i);}protected V init(int i){ return e(); }abstract V e();abstract V agg(V v0,V v1);abstract V map(V v,F f,int l,int r);abstract F comp(F f0,F f1);protected V eval(int i){if (i < n && lazy[i] != null) {rangeMap(i);prop(i <<1,lazy[i]);prop(i <<1 |1,lazy[i]);lazy[i] = null;}return val[i];}private void merge(int i){ val[i] = agg(eval(i <<1),eval(i <<1 |1)); }protected void rangeMap(int i){ val[i] = map(val[i],lazy[i],l[i],r[i]); }protected void prop(int i,F f){if (i < n)lazy[i] = lazy[i] == null ? f : comp(lazy[i],f);elseval[i] = map(val[i],f,l[i],r[i]);}protected void up(int l,int r){l = oddPart(l +n);r = oddPart(r +n);while (1 < l)merge(l >>= 1);while (1 < r)merge(r >>= 1);}protected void down(int l,int r){l = oddPart(l +n);r = oddPart(r +n);for (int i = log;i > 0;i--) {if (l >>i > 0)eval(l >>i);if (r >>i > 0)eval(r >>i);}}private int oddPart(int i){ return i /(i &-i); }protected void upd(int i,F f){ prop(i +n,f); }protected void upd(int l,int r,F f){l += n;r += n;do {if ((l &1) == 1)prop(l++,f);if ((r &1) == 1)prop(--r,f);} while ((l >>= 1) < (r >>= 1));}protected V get(int i){ return val[i +n]; }protected V get(int l,int r){l += n;r += n;V vl = e(),vr = e();do {vl = (l &1) == 0 ? vl : agg(vl,eval(l++));vr = (r &1) == 0 ? vr : agg(eval(--r),vr);} while ((l >>= 1) < (r >>= 1));return agg(vl,vr);}}abstract class SegmentTree<V, F> extends Seg<V, F>{SegmentTree(int n){ super(n); }@Overrideprotected F comp(F f0,F f1){ return null; }@Overrideprotected void upd(int i,F f){super.upd(i,f);up(i,i +1);}}class DeletablePque<T> {private Queue<T> que,rem;private Comparator<T> cmp;@SuppressWarnings("unchecked")public DeletablePque(){ this((Comparator<T>) Comparator.naturalOrder()); }public <U extends Comparable<U>> DeletablePque(Function<T, U> func){ this(Comparator.comparing(func)); }private DeletablePque(Comparator<T> cmp){this.cmp = cmp;que = new PriorityQueue<>(cmp);rem = new PriorityQueue<>(cmp);}public boolean add(T t){ return que.add(t); }public boolean remove(T t){ return rem.add(t); }public T poll(){ return adj().poll(); }public T peek(){ return adj().peek(); }private Queue<T> adj(){while (!que.isEmpty() && !rem.isEmpty()&& cmp.compare(que.peek(),rem.peek()) == 0) {que.poll();rem.poll();}return que;}}class Mex{private int[] cnt;private DeletablePque<Integer> que;private Queue<Integer> wait;private int add;public Mex(){ this(16); }public Mex(int n){cnt = new int[n];que = new DeletablePque<>();wait = new PriorityQueue<>();for (int x = 0;x < cnt.length;x++)que.add(x);}public int add(int x){if (++add == cnt.length)grow();if (x < cnt.length) {if (cnt[x]++ == 0)que.remove(x);} elsewait.add(x);return que.peek();}public int remove(int x){if (x < cnt.length && --cnt[x] == 0)que.add(x);return que.peek();}private void grow(){for (int x = cnt.length;x < cnt.length <<1;x++)que.add(x);for (cnt = copyOf(cnt,cnt.length <<1);!wait.isEmpty() && wait.peek() < cnt.length;add--)add(wait.poll());}}abstract class Dijkstra<E, L> extends Graph<E>{protected L[] len;private int[] arr,rev;private int sz;protected Edge<E>[] pre;private Comparator<L> cmp;protected L zero,inf;@SuppressWarnings("unchecked")public Dijkstra(int n,boolean dir){ this(n,dir,(Comparator<L>) Comparator.naturalOrder()); }public <U extends Comparable<U>> Dijkstra(int n,boolean dir,Function<L, U> func){this(n,dir,Comparator.comparing(func));}@SuppressWarnings("unchecked")public Dijkstra(int n,boolean dir,Comparator<L> cmp){super(n,dir);this.cmp = cmp;zero = zero();inf = inf();len = (L[]) new Object[n];arr = new int[n];rev = new int[n];pre = new Edge[n];}protected abstract L zero();protected abstract L inf();protected abstract L f(L l,E val);public void calcFrom(int s){ calc(s,-1); }public void calc(int s,int g){init();pre[s] = null;set(s,zero);while (!isEmpty()) {var cur = poll();if (cur == g)break;L l = len[cur];for (var e:go(cur)) {L ll = f(l,e.val);if (cmp.compare(ll,len[e.v]) < 0) {pre[e.v] = e;set(e.v,ll);}}}}public L len(int t){ return len[t]; }public Deque<Edge<E>> path(int t){Deque<Edge<E>> ret = new ArrayDeque<>();while (pre[t] != null) {ret.addFirst(pre[t]);t = pre[t].u;}return ret;}private void init(){fill(len,inf);setAll(arr,i -> i);setAll(rev,i -> i);sz = n;}private boolean isEmpty(){ return sz == 0; }private void set(int i,L l){if (sz <= rev[i] || cmp.compare(len[i],l) <= 0)return;len[i] = l;heapfy(rev[i]);}private int poll(){int ret = arr[0];heapfy(swap(0,--sz));return ret;}private void heapfy(int k){int p = k -1 >>1;if (0 <= p && cmp.compare(len[arr[p]],len[arr[k]]) > 0) {heapfy(swap(p,k));return;}int c = k <<1 |1;if (sz <= c)return;if (c +1 < sz && cmp.compare(len[arr[c +1]],len[arr[c]]) < 0)c++;if (cmp.compare(len[arr[c]],len[arr[k]]) < 0)heapfy(swap(c,k));}private int swap(int i,int j){int t = arr[i];arr[i] = arr[j];arr[j] = t;rev[arr[i]] = i;rev[arr[j]] = j;return i;}}class Edge<L> {int id,u,v;L val;Edge<L> re;Edge(int id,int u,int v,L val){this.id = id;this.u = u;this.v = v;this.val = val;}@Overridepublic String toString(){ return "(" +u +"," +v +"," +val +")"; }}class UnionFind{int num;int[] dat;int[] nxt;long[]val;public UnionFind(int n,long[] val){dat = new int[n];nxt = new int[n];setAll(nxt,i -> i);fill(dat,-1);num = n;this.val = val;}int root(int x){ return dat[x] < 0 ? x : (dat[x] = root(dat[x])); }boolean same(int u,int v){ return root(u) == root(v); }boolean unite(int u,int v){if ((u = root(u)) == (v = root(v)))return false;if (dat[u] > dat[v]) {u ^= v;v ^= u;u ^= v;}dat[u] += dat[v];val[u] += val[v];dat[v] = u;num--;nxt[u] ^= nxt[v];nxt[v] ^= nxt[u];nxt[u] ^= nxt[v];return true;}int size(int x){ return -dat[root(x)]; }int[] getGroup(int x){int[] ret = new int[size(x)];for (int i = 0,c = root(x);i < ret.length;i++)ret[i] = c = nxt[c];return ret;}}class Graph<L> {public int n;List<Edge<L>> es;private List<Edge<L>>[] go,bk;@SuppressWarnings("unchecked")public Graph(int n,boolean dir){this.n = n;go = new List[n];bk = dir ? new List[n] : go;for (int i = 0;i < n;i++) {go[i] = new ArrayList<>();bk[i] = new ArrayList<>();}es = new ArrayList<>();}public void addEdge(int u,int v){ addEdge(u,v,null); }public void addEdge(int u,int v,L l){var e = new Edge<>(es.size(),u,v,l);var re = new Edge<>(e.id,e.v,e.u,inv(e.val));es.add(e);go[u].add(re.re = e);bk[v].add(e.re = re);}protected L inv(L l){ return l; }public List<Edge<L>> go(int ui){ return go[ui]; }public List<Edge<L>> back(int ui){ return bk[ui]; }}class Util{static int[] arrI(int N,IntUnaryOperator f){int[] ret = new int[N];setAll(ret,f);return ret;}static long[] arrL(int N,IntToLongFunction f){long[] ret = new long[N];setAll(ret,f);return ret;}static double[] arrD(int N,IntToDoubleFunction f){double[] ret = new double[N];setAll(ret,f);return ret;}static <T> T[] arr(T[] arr,IntFunction<T> f){setAll(arr,f);return arr;}}class MyReader{private byte[] buf = new byte[1 <<16];private int ptr,tail;private InputStream in;MyReader(InputStream in){ this.in = in; }private byte read(){if (ptr == tail)try {tail = in.read(buf);ptr = 0;} catch (IOException e) {}return buf[ptr++];}private boolean isPrintable(byte c){ return 32 < c && c < 127; }private byte nextPrintable(){byte ret = read();while (!isPrintable(ret))ret = read();return ret;}int it(){ return toIntExact(lg()); }int[] it(int N){ return Util.arrI(N,i -> it()); }int[][] it(int H,int W){ return Util.arr(new int[H][],i -> it(W)); }int idx(){ return it() -1; }int[] idx(int N){ return Util.arrI(N,i -> idx()); }int[][] idx(int H,int W){ return Util.arr(new int[H][],i -> idx(W)); }long lg(){byte i = nextPrintable();boolean negative = i == 45;long n = negative ? 0 : i -'0';while (isPrintable(i = read()))n = 10 *n +i -'0';return negative ? -n : n;}long[] lg(int N){ return Util.arrL(N,i -> lg()); }long[][] lg(int H,int W){ return Util.arr(new long[H][],i -> lg(W)); }double dbl(){ return Double.parseDouble(str()); }double[] dbl(int N){ return Util.arrD(N,i -> dbl()); }double[][] dbl(int H,int W){ return Util.arr(new double[H][],i -> dbl(W)); }char[] ch(){ return str().toCharArray(); }char[][] ch(int H){ return Util.arr(new char[H][],i -> ch()); }String line(){StringBuilder sb = new StringBuilder();for (byte c;(c = read()) != '\n';)sb.append((char) c);return sb.toString();}String str(){StringBuilder sb = new StringBuilder();sb.append((char) nextPrintable());for (byte c;isPrintable(c = read());)sb.append((char) c);return sb.toString();}String[] str(int N){ return Util.arr(new String[N],i -> str()); }}class MyWriter{private OutputStream out;private byte[] buf = new byte[1 <<16],ibuf = new byte[20];private int tail;MyWriter(OutputStream out){ this.out = out; }void flush(){try {out.write(buf,0,tail);tail = 0;} catch (IOException e) {e.printStackTrace();}}protected void ln(){ write((byte) '\n'); }private void write(byte b){buf[tail++] = b;if (tail == buf.length)flush();}private void write(byte[] b,int off,int len){for (int i = off;i < off +len;i++)write(b[i]);}private void write(long n){if (n < 0) {n = -n;write((byte) '-');}int i = ibuf.length;do {ibuf[--i] = (byte) (n %10 +'0');n /= 10;} while (n > 0);write(ibuf,i,ibuf.length -i);}private void print(Object obj){if (obj instanceof Boolean)print((boolean) obj ? Solver.yes : Solver.no);else if (obj instanceof Integer)write((int) obj);else if (obj instanceof Long)write((long) obj);else if (obj instanceof char[] cs)for (char b:cs)write((byte) b);else if (obj.getClass().isArray()) {int l = Array.getLength(obj);for (int i = 0;i < l;i++) {print(Array.get(obj,i));if (i +1 < l)write((byte) ' ');}} elseprint(Objects.toString(obj).toCharArray());}void println(Object obj){if (obj == null)return;if (obj instanceof Iterable<?> co)for (Object e:co)println(e);else if (obj.getClass().isArray() && Array.getLength(obj) > 0 && Array.get(obj,0).getClass().isArray()) {int l = Array.getLength(obj);for (int i = 0;i < l;i++)println(Array.get(obj,i));} else {print(obj);ln();}}void printlns(Object... o){print(o);ln();}}class Main{public static void main(String[] args) throws Exception{new Solver(){public void exe(){out.println(solve());out.flush();log.println(elapsed());}}.exe();}}