結果

問題 No.1602 With Animals into Institute 2
ユーザー 草苺奶昔草苺奶昔
提出日時 2023-02-27 11:19:05
言語 Go
(1.22.1)
結果
AC  
実行時間 1,234 ms / 4,000 ms
コード長 5,504 bytes
コンパイル時間 14,533 ms
コンパイル使用メモリ 210,200 KB
実行使用メモリ 46,476 KB
最終ジャッジ日時 2023-10-12 21:44:40
合計ジャッジ時間 31,175 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,352 KB
testcase_01 AC 1 ms
4,348 KB
testcase_02 AC 1 ms
4,352 KB
testcase_03 AC 11 ms
4,348 KB
testcase_04 AC 12 ms
4,368 KB
testcase_05 AC 16 ms
5,636 KB
testcase_06 AC 751 ms
36,032 KB
testcase_07 AC 719 ms
36,176 KB
testcase_08 AC 1,234 ms
44,460 KB
testcase_09 AC 1,084 ms
43,468 KB
testcase_10 AC 1,096 ms
43,524 KB
testcase_11 AC 1,098 ms
43,520 KB
testcase_12 AC 998 ms
42,828 KB
testcase_13 AC 1,013 ms
44,064 KB
testcase_14 AC 1,028 ms
43,812 KB
testcase_15 AC 1,032 ms
46,108 KB
testcase_16 AC 1,017 ms
46,476 KB
testcase_17 AC 1,036 ms
44,080 KB
testcase_18 AC 13 ms
4,368 KB
testcase_19 AC 14 ms
4,372 KB
testcase_20 AC 14 ms
5,636 KB
testcase_21 AC 13 ms
4,372 KB
testcase_22 AC 13 ms
4,372 KB
testcase_23 AC 13 ms
4,372 KB
testcase_24 AC 13 ms
4,368 KB
testcase_25 AC 13 ms
4,372 KB
testcase_26 AC 13 ms
4,372 KB
testcase_27 AC 2 ms
4,372 KB
testcase_28 AC 1 ms
4,376 KB
testcase_29 AC 1 ms
4,372 KB
testcase_30 AC 1 ms
4,372 KB
testcase_31 AC 2 ms
4,372 KB
testcase_32 AC 1 ms
4,368 KB
testcase_33 AC 2 ms
4,372 KB
testcase_34 AC 2 ms
4,376 KB
testcase_35 AC 2 ms
4,372 KB
testcase_36 AC 1 ms
4,368 KB
testcase_37 AC 2 ms
4,368 KB
testcase_38 AC 1 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	var n, m, k int
	fmt.Fscan(in, &n, &m, &k)
	e := func() Label { return 0 }
	op := func(label1, label2 Label) Label { return label1 ^ label2 }
	g := NewShortestNonzeroPath(n, e, op)
	for i := 0; i < m; i++ {
		var u, v, cost int
		var s string
		fmt.Fscan(in, &u, &v, &cost, &s)
		u, v = u-1, v-1
		label := 0
		for j := 0; j < k; j++ {
			if s[j] == '1' {
				label |= 1 << j
			}
		}
		g.AddUndirectedEdge(u, v, cost, label)
	}

	res := g.Build(n - 1)
	for i := 0; i <= n-2; i++ {
		if res[i] == INF {
			fmt.Fprintln(out, -1)
		} else {
			fmt.Fprintln(out, res[i])
		}
	}

}

const INF int = 1e18

type Label = int

type ShortestNonzeroPath struct {
	g  [][]edge
	e  func() Label
	op func(Label, Label) Label
	uf []int
}

type edge = struct {
	to    int
	cost  int
	label Label
}

type SP struct {
	dist   []int
	depth  []int
	parent []int
	label  []Label
}

func NewShortestNonzeroPath(n int, e func() Label, op func(label1, label2 Label) Label) *ShortestNonzeroPath {
	return &ShortestNonzeroPath{g: make([][]edge, n), e: e, op: op}
}

func (s *ShortestNonzeroPath) AddUndirectedEdge(u, v, cost int, label Label) {
	s.AddDirectedEdge(u, v, cost, label)
	s.AddDirectedEdge(v, u, cost, label)
}

func (s *ShortestNonzeroPath) AddDirectedEdge(u, v, cost int, label Label) {
	s.g[u] = append(s.g[u], edge{v, cost, label})
}

func (snp *ShortestNonzeroPath) Build(start int) (dist []int) {
	n := len(snp.g)
	sp := snp.dijkstra(start)
	snp.uf = make([]int, n)
	for i := range snp.uf {
		snp.uf[i] = -1
	}

	type tuple = [3]int
	pq := NewHeap(func(a, b H) int {
		return a.(tuple)[0] - b.(tuple)[0]
	}, nil)
	for u := 0; u < n; u++ {
		if sp.dist[u] != INF {
			for i := range snp.g[u] {
				e := snp.g[u][i]
				if u < e.to && snp.op(sp.label[u], e.label) != sp.label[e.to] {
					pq.Push(tuple{sp.dist[u] + sp.dist[e.to] + e.cost, u, i})
				}
			}
		}
	}

	dist = make([]int, n)
	for i := range dist {
		dist[i] = INF
	}
	bs := []int{}
	for pq.Len() > 0 {
		tmp := pq.Pop().(tuple)
		cost, u0, i := tmp[0], tmp[1], tmp[2]
		v0 := snp.g[u0][i].to
		u, v := snp.findUf(u0), snp.findUf(v0)
		for u != v {
			if sp.depth[u] > sp.depth[v] {
				bs = append(bs, u)
				u = snp.findUf(sp.parent[u])
			} else {
				bs = append(bs, v)
				v = snp.findUf(sp.parent[v])
			}
		}
		for _, x := range bs {
			snp.uniteUf(u, x)
			dist[x] = cost - sp.dist[x]
			for j := range snp.g[x] {
				e := snp.g[x][j]
				if snp.op(sp.label[x], e.label) == sp.label[e.to] {
					pq.Push(tuple{dist[x] + sp.dist[e.to] + e.cost, x, j})
				}
			}
		}
		bs = bs[:0]
	}

	for i := 0; i < n; i++ {
		if sp.label[i] != snp.e() && sp.dist[i] < dist[i] {
			dist[i] = sp.dist[i]
		}
	}

	return
}

func (snp *ShortestNonzeroPath) dijkstra(s int) *SP {
	n := len(snp.g)
	type pair = [2]int
	dist := make([]int, n)
	for i := range dist {
		dist[i] = INF
	}
	depth, parent := make([]int, n), make([]int, n)
	for i := range parent {
		parent[i] = -1
		depth[i] = -1
	}
	label := make([]Label, n)
	for i := range label {
		label[i] = snp.e()
	}

	pq := NewHeap(func(a, b H) int {
		return a.([2]int)[0] - b.([2]int)[0]
	}, nil)
	pq.Push(pair{0, s})
	dist[s] = 0
	depth[s] = 0

	for pq.Len() > 0 {
		p := pq.Pop().([2]int)
		cost, cur := p[0], p[1]
		if dist[cur] < cost {
			continue
		}
		for _, e := range snp.g[cur] {
			to, nextCost := e.to, cost+e.cost
			if dist[to] > nextCost {
				dist[to] = nextCost
				parent[to] = cur
				depth[to] = depth[cur] + 1
				label[to] = snp.op(label[cur], e.label)
				pq.Push(pair{nextCost, to})
			}
		}
	}

	return &SP{dist, depth, parent, label}
}

func (s *ShortestNonzeroPath) findUf(k int) int {
	if s.uf[k] == -1 {
		return k
	}
	s.uf[k] = s.findUf(s.uf[k])
	return s.uf[k]
}

func (s *ShortestNonzeroPath) uniteUf(r, c int) {
	s.uf[c] = r
}

type H = interface{}

// Should return a number:
//    negative , if a < b
//    zero     , if a == b
//    positive , if a > b
type Comparator func(a, b H) int

func NewHeap(comparator Comparator, nums []H) *Heap {
	nums = append(nums[:0:0], nums...)
	heap := &Heap{comparator: comparator, data: nums}
	heap.heapify()
	return heap
}

type Heap struct {
	data       []H
	comparator Comparator
}

func (h *Heap) Push(value H) {
	h.data = append(h.data, value)
	h.pushUp(h.Len() - 1)
}

func (h *Heap) Pop() (value H) {
	if h.Len() == 0 {
		return
	}

	value = h.data[0]
	h.data[0] = h.data[h.Len()-1]
	h.data = h.data[:h.Len()-1]
	h.pushDown(0)
	return
}

func (h *Heap) Peek() (value H) {
	if h.Len() == 0 {
		return
	}
	value = h.data[0]
	return
}

func (h *Heap) Len() int { return len(h.data) }

func (h *Heap) heapify() {
	n := h.Len()
	for i := (n >> 1) - 1; i > -1; i-- {
		h.pushDown(i)
	}
}

func (h *Heap) pushUp(root int) {
	for parent := (root - 1) >> 1; parent >= 0 && h.comparator(h.data[root], h.data[parent]) < 0; parent = (root - 1) >> 1 {
		h.data[root], h.data[parent] = h.data[parent], h.data[root]
		root = parent
	}
}

func (h *Heap) pushDown(root int) {
	n := h.Len()
	for left := (root<<1 + 1); left < n; left = (root<<1 + 1) {
		right := left + 1
		minIndex := root

		if h.comparator(h.data[left], h.data[minIndex]) < 0 {
			minIndex = left
		}

		if right < n && h.comparator(h.data[right], h.data[minIndex]) < 0 {
			minIndex = right
		}

		if minIndex == root {
			return
		}

		h.data[root], h.data[minIndex] = h.data[minIndex], h.data[root]
		root = minIndex
	}
}
0