Codeforces 567E — President and Roads

1package main2 3import (4	"bufio"5	"container/heap"6	. "fmt"7	"io"8)9 10// github.com/EndlessCheng/codeforces-go11type pair67 struct {12	v int13	d int6414}15type hp67 []pair6716 17func (h hp67) Len() int              { return len(h) }18func (h hp67) Less(i, j int) bool    { return h[i].d < h[j].d }19func (h hp67) Swap(i, j int)         { h[i], h[j] = h[j], h[i] }20func (h *hp67) Push(v interface{})   { *h = append(*h, v.(pair67)) }21func (h *hp67) Pop() (v interface{}) { a := *h; *h, v = a[:len(a)-1], a[len(a)-1]; return }22func (h *hp67) push(v pair67)        { heap.Push(h, v) }23func (h *hp67) pop() pair67          { return heap.Pop(h).(pair67) }24 25func CF567E(_r io.Reader, _w io.Writer) {26	in := bufio.NewReader(_r)27	out := bufio.NewWriter(_w)28	defer out.Flush()29	min := func(a, b int) int {30		if a < b {31			return a32		}33		return b34	}35 36	var n, m, s, t, v, w, wt int37	Fscan(in, &n, &m, &s, &t)38	s--39	t--40	type edge struct {41		v, w, wt int42		isB      bool43	}44	es := make([]edge, m)45	type nb struct{ to, wt int }46	g := make([][]nb, n)47	g2 := make([][]nb, n)48	for i := range es {49		Fscan(in, &v, &w, &wt)50		v--51		w--52		es[i] = edge{v, w, wt, false}53		g[v] = append(g[v], nb{w, wt})54		g2[w] = append(g2[w], nb{v, wt})55	}56 57	dij := func(g [][]nb, st int) []int64 {58		dis := make([]int64, n)59		for i := range dis {60			dis[i] = 1e1861		}62		dis[st] = 063		h := hp67{{st, 0}}64		for len(h) > 0 {65			vd := h.pop()66			v := vd.v67			if dis[v] < vd.d {68				continue69			}70			for _, e := range g[v] {71				w, wt := e.to, int64(e.wt)72				if newD := dis[v] + wt; newD < dis[w] {73					dis[w] = newD74					h.push(pair67{w, newD})75				}76			}77		}78		return dis79	}80	ds, dt := dij(g, s), dij(g2, t)81 82	// 将所有在最短路上的边组成一无向图 g3，跑割边，求出 YES。非割边就只能减 1 了，如果边权就是 1 则为 NO83	g3 := make([][]nb, n)84	for i, e := range es {85		if v, w := e.v, e.w; ds[v]+int64(e.wt)+dt[w] == ds[t] {86			g3[v] = append(g3[v], nb{w, i})87			g3[w] = append(g3[w], nb{v, i})88		}89	}90	dfn := make([]int, n)91	ts := 092	var f func(int, int) int93	f = func(v, fid int) int {94		ts++95		dfn[v] = ts96		lowV := ts97		for _, e := range g3[v] {98			if w := e.to; dfn[w] == 0 {99				lowW := f(w, e.wt)100				if lowW > dfn[v] {101					es[e.wt].isB = true102				}103				lowV = min(lowV, lowW)104			} else if e.wt != fid {105				lowV = min(lowV, dfn[w])106			}107		}108		return lowV109	}110	for v, t := range dfn {111		if t == 0 {112			f(v, -1)113		}114	}115 116	for _, e := range es {117		v, w, wt := e.v, e.w, int64(e.wt)118		if d := ds[v] + wt + dt[w] - ds[t]; d == 0 {119			if e.isB {120				Fprintln(out, "YES")121			} else if wt > 1 {122				Fprintln(out, "CAN 1")123			} else {124				Fprintln(out, "NO")125			}126		} else if wt > d+1 {127			Fprintln(out, "CAN", d+1)128		} else {129			Fprintln(out, "NO")130		}131	}132}133 134//func main() { CF567E(os.Stdin, os.Stdout) }135