結果

問題 No.160 最短経路のうち辞書順最小
コンテスト
ユーザー aru aru
提出日時 2020-08-27 22:10:43
言語 Go
(1.23.4)
結果
WA  
実行時間 -
コード長 3,135 bytes
コンパイル時間 14,413 ms
コンパイル使用メモリ 234,188 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-08 11:02:25
合計ジャッジ時間 15,829 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 4 WA * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

package main

import (
	"bufio"
	"container/heap"
	"fmt"
	"os"
	"sort"
	"strconv"
)

func out(x ...interface{}) {
	fmt.Println(x...)
}

var sc = bufio.NewScanner(os.Stdin)

func getInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func getInts(N int) []int {
	ret := make([]int, N)
	for i := 0; i < N; i++ {
		ret[i] = getInt()
	}
	return ret
}

func getString() string {
	sc.Scan()
	return sc.Text()
}

// min, max, asub, absなど基本関数
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func asub(a, b int) int {
	if a > b {
		return a - b
	}
	return b - a
}

func abs(a int) int {
	if a >= 0 {
		return a
	}
	return -a
}

func lowerBound(a []int, x int) int {
	idx := sort.Search(len(a), func(i int) bool {
		return a[i] >= x
	})
	return idx
}

func upperBound(a []int, x int) int {
	idx := sort.Search(len(a), func(i int) bool {
		return a[i] > x
	})
	return idx
}

//---------------------------------------------
// priority queue
//---------------------------------------------
type pqi struct{ a, to int }

type priorityQueue []pqi

func (pq priorityQueue) Len() int      { return len(pq) }
func (pq priorityQueue) Swap(i, j int) { pq[i], pq[j] = pq[j], pq[i] }
func (pq priorityQueue) Less(i, j int) bool {
	if pq[i].a == pq[j].a {
		return pq[i].to < pq[j].to
	}
	return pq[i].a < pq[j].a
}
func (pq *priorityQueue) Push(x interface{}) { *pq = append(*pq, x.(pqi)) }
func (pq *priorityQueue) Pop() interface{} {
	x := (*pq)[len(*pq)-1]
	*pq = (*pq)[0 : len(*pq)-1]
	return x
}

type edge struct {
	to, cost int
}

var N, M, S, G int
var node [][]edge

const inf = int(1e15)

func dijkstra(s, g int) {
	dist := make([]int, N)
	for i := 0; i < N; i++ {
		dist[i] = inf
	}
	route := make([][]int, N)
	pq := priorityQueue{}
	dist[s] = 0
	heap.Push(&pq, pqi{0, s})
	for len(pq) != 0 {
		e := pq[0].to
		// out(e, pq)
		heap.Pop(&pq)
		for _, v := range node[e] {
			if dist[v.to] == dist[e]+v.cost {
				// out("SAME", v.to, route[v.to], append(route[e], e), dist[v.to])
				x := append(route[v.to], v.to)
				y := append(append(route[e], e), v.to)
				if len(x) > len(y) {
					x, y = y, x
				}
				small := x
				for i := 0; i < len(x); i++ {
					if x[i] > y[i] {
						small = y
						break
					}
				}
				// out(small)
				route[v.to] = small[:len(small)-1]
			}
			if dist[v.to] > dist[e]+v.cost {
				dist[v.to] = dist[e] + v.cost
				heap.Push(&pq, pqi{dist[v.to], v.to})
				route[v.to] = append(route[e], e)
			}
		}
	}
	// out(dist)
	// out(route)
	for _, e := range route[G] {
		fmt.Print(e, " ")
	}
	fmt.Println(G)
}

func main() {
	sc.Split(bufio.ScanWords)
	N, M, S, G = getInt(), getInt(), getInt(), getInt()
	node = make([][]edge, N)
	for i := 0; i < M; i++ {
		a, b, c := getInt(), getInt(), getInt()
		node[a] = append(node[a], edge{b, c})
		node[b] = append(node[b], edge{a, c})
	}
	for i := 0; i < N; i++ {
		sort.Slice(node[i], func(j, k int) bool {
			return node[i][j].to < node[i][k].to
		})
	}
	// for i := 0; i < N; i++ {
	// 	out(i, node[i])
	// }

	dijkstra(S, G)

}
0