結果
問題 |
No.2805 Go to School
|
ユーザー |
![]() |
提出日時 | 2025-04-09 13:42:20 |
言語 | Go (1.23.4) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 2,208 bytes |
コンパイル時間 | 12,372 ms |
コンパイル使用メモリ | 237,704 KB |
実行使用メモリ | 27,276 KB |
最終ジャッジ日時 | 2025-04-09 15:44:32 |
合計ジャッジ時間 | 23,738 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 35 WA * 1 |
ソースコード
package main import . "fmt" import . "os" import bf "bufio" import "container/heap" func main() { rd := bf.NewReader(Stdin) var n,m,l int var s,e int64 Fscan(rd,&n,&m,&l,&s,&e) edges := make([][]*Edge, n+1) for i := 0; i < m; i++ { var a, b int var cost int64 Fscan(rd, &a, &b, &cost) edges[a] = append(edges[a], &Edge{b, cost}) edges[b] = append(edges[b], &Edge{a, cost}) } toilet := make([]bool, n+1) for i := 0; i < l; i++ { var t int Fscan(rd, &t) toilet[t] = true } toCosts := make([]int64, n+1) for i := range toCosts { toCosts[i] = 1e18 } pq := make(PQ, 0, n+1) heap.Push(&pq, &Item{1, 0}) toCosts[1] = 0 for pq.Len() > 0 { item := heap.Pop(&pq).(*Item) if item.cost > toCosts[item.id] { continue } for _, e := range edges[item.id] { cost := item.cost + e.cost if cost < toCosts[e.to] { toCosts[e.to] = cost heap.Push(&pq, &Item{e.to, cost}) } } } rvCosts := make([]int64, n+1) for i := range rvCosts { rvCosts[i] = 1e18 } pq = pq[:0] heap.Push(&pq, &Item{n, 0}) rvCosts[n] = 0 for pq.Len() > 0 { item := heap.Pop(&pq).(*Item) if item.cost > rvCosts[item.id] { continue } for _, e := range edges[item.id] { cost := item.cost + e.cost if cost < rvCosts[e.to] { rvCosts[e.to] = cost heap.Push(&pq, &Item{e.to, cost}) } } } // Println(toCosts) // Println(rvCosts) var ans int64 = 1e18 for i := 1; i <= n; i++ { if !toilet[i] { continue } if toCosts[i] > s + e { continue } cost := max(toCosts[i], s) + 1 + rvCosts[i] ans = min(ans, cost) } if ans < 1e18 { Println(ans) } else { Println(-1) } } func max(a, b int64) int64 { if a > b { return a } else { return b } } func min(a, b int64) int64 { if a < b { return a } else { return b } } type Edge struct { to int cost int64 } type Item struct { id int cost int64 } type PQ []*Item func (q PQ) Len() int { return len(q) } func (q PQ) Less(i, j int) bool { return q[i].cost < q[j].cost } func (q PQ) Swap(i, j int) { q[i], q[j] = q[j], q[i] } func (q *PQ) Push(x any) { *q = append(*q, x.(*Item)) } func (q *PQ) Pop() any { old := *q n := len(old) x := old[n-1] *q = old[:n-1] return x }