結果

問題 No.1344 Typical Shortest Path Sum
コンテスト
ユーザー ID 21712
提出日時 2026-05-27 19:28:14
言語 Go
(1.26.1)
コンパイル:
env GOCACHE=/tmp go build _filename_
実行:
./Main
結果
AC  
実行時間 16 ms / 2,000 ms
コード長 4,331 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 10,828 ms
コンパイル使用メモリ 282,004 KB
実行使用メモリ 6,400 KB
最終ジャッジ日時 2026-05-27 19:28:35
合計ジャッジ時間 13,263 ms
ジャッジサーバーID
（参考情報） 		judge2_1 / judge3_1
純コード判定待ち
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 77
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

package main

import . "fmt"
import "container/heap"

type E struct {
	s,t,d int
}

func main() {
	var n,m int
	Scan(&n,&m)
	edges := make([]*E, m)
	for i := range edges {
		e := new(E)
		Scan(&e.s, &e.t, &e.d)
		e.s--
		e.t--
		edges[i] = e
	}
	for _, ans := range solve(n,m, edges) {
		Println(ans)
	}
}

func solve(n, m int, edges []*E) []int {
	
	paths, _ := JohnsonsAlgorithm(n, edges)
	
	ans := make([]int, n)
	for i, ps := range paths {
		sum := 0
		for _, p := range ps {
			if p.dist != INF {
				sum += p.dist
			}
		}
		ans[i] = sum
	}
	
	return ans
}

const INF int = 1e18+1

type P struct {
	dist int
	from *E
}

func BellmanFordAlgorithm(vertexCount, startVertexId int, edges []*E) ([]*P,bool) {
	ps := make([]*P, vertexCount)
	for i := range ps {
		ps[i] = new(P)
		if i != startVertexId {
			ps[i].dist = INF
		}
	}
	for i := 0; i < vertexCount; i++ {
		for _, e := range edges {
			s := ps[e.s]
			t := ps[e.t]
			if t.dist > s.dist + e.d {
				t.dist = s.dist + e.d
				t.from = e
			}
		}
	}
	for _, e := range edges {
		if ps[e.t].dist > ps[e.s].dist + e.d {
			return nil, false
		}
	}
	return ps, true
}

func JohnsonsAlgorithm(vertexCount int, edges []*E) ([][]*P, bool) {
	qVertexId := vertexCount
	qEdges := make([]*E, len(edges)+vertexCount)
	copy(qEdges[:len(edges)], edges)
	for i := 0; i < vertexCount; i++ {
		e := new(E)
		e.s = qVertexId
		e.t = i
		e.d = 0
		qEdges[i+len(edges)] = e
	}
	qPaths, ok := BellmanFordAlgorithm(vertexCount+1, qVertexId, qEdges)
	if !ok {
		return nil, false
	}
	dEdges := make([][]*E, vertexCount)
	for i, e := range edges {
		ne := new(E)
		ne.s = i
		ne.t = e.t
		ne.d = e.d + qPaths[e.s].dist - qPaths[e.t].dist
		dEdges[e.s] = append(dEdges[e.s], ne)
	}
	pps := make([][]*P, vertexCount)
	items := make([]*Item, vertexCount)
	for i := range items {
		items[i] = newItem(i)
	}
	for id := 0; id < vertexCount; id++ {
		ps := make([]*P, vertexCount)
		pps[id] = ps
		dists := make([]int, vertexCount)
		for i := range ps {
			ps[i] = new(P)
			if i != id {
				ps[i].dist = INF
				dists[i] = INF
			}
		}
		pq := newPQ(vertexCount, func(a, b any) bool {
			return dists[a.(int)] < dists[b.(int)]
		})
		heap.Push(pq, items[id])
		for pq.Len() > 0 {
			curId := heap.Pop(pq).(*Item).value.(int)
			for _, e := range dEdges[curId] {
				d := dists[curId] + e.d
				if dists[e.t] <= d {
					continue
				}
				dists[e.t] = d
				ps[e.t].dist = ps[curId].dist + edges[e.s].d
				ps[e.t].from = edges[e.s]
				if items[e.t].index < 0 {
					heap.Push(pq, items[e.t])
				} else {
					heap.Fix(pq, items[e.t].index)
				}
			}
		}
	}
	return pps,true
}

func DijkstrasAlgorightm(vertexCount, startVertexId int, edges []*E) []*P {
	dEdges := make([][]*E, vertexCount)
	for _, e := range edges {
		dEdges[e.s] = append(dEdges[e.s], e)
	}
	ps := make([]*P, vertexCount)
	for i := range ps {
		ps[i] = new(P)
		if i != startVertexId {
			ps[i].dist = INF
		}
	}
	pq := newPQ(vertexCount, func(a, b any) bool {
		return ps[a.(int)].dist < ps[b.(int)].dist
	})
	items := make([]*Item, vertexCount)
	for i := range items {
		items[i] = newItem(i)
	}
	heap.Push(pq, items[startVertexId])
	for pq.Len() > 0 {
		id := pq.Pop().(*Item).value.(int)
		for _, e := range dEdges[id] {
			d := ps[id].dist + e.d
			if ps[e.t].dist <= d {
				continue
			}
			ps[e.t].dist = d
			ps[e.t].from = e
			if items[e.t].index < 0 {
				heap.Push(pq, items[e.t])
			} else {
				heap.Fix(pq, items[e.t].index)
			}
		}
	}
	return ps
}

type Item struct {
	value any
	index int
}

func newItem(value any) *Item {
	return &Item{ value: value, index: -1 }
}

type PQ struct {
	less func(a, b any) bool
	items []*Item
}

func newPQ(initialCapacity int, less func(a, b any) bool) *PQ {
	return &PQ{
		less: less,
		items: make([]*Item, 0, initialCapacity),
	}
}

func (pq PQ) Len() int { return len(pq.items) }
func (pq PQ) Swap(i, j int) {
	pq.items[i], pq.items[j] = pq.items[j], pq.items[i]
	pq.items[i].index = i
	pq.items[j].index = j
}
func (pq PQ) Less(i, j int) bool { return pq.less(pq.items[i].value, pq.items[j].value) }
func (pq *PQ) Push(v any) {
	item := v.(*Item)
	n := len(pq.items)
	item.index = n
	pq.items = append(pq.items, item)
}
func (pq *PQ) Pop() any {
	old := pq.items
	n := len(old)
	item := old[n-1]
	item.index = -1
	old[n-1] = nil
	pq.items = old[:n-1]
	return item
}
0