發表新討論
#15115: 關於這一題的解法


rollfc (胖胖貓)

學校 : 國立清華大學
編號 : 81012
來源 : [36.229.36.84]
最後登入時間 ：
2024-05-04 14:24:04
d908. 4. 最佳路徑 -- 99學年度北基區資訊學科能力競賽 | From: [140.113.208.181] | 發表日期 : 2018-09-14 16:33

不好意思, 想問一下高手們這個題目中

一開始我用 Priority Queue

Queue裡面的排序方式是 到達其他點的權重

因此作為下一次展開的選擇都是 Queue裡面的最大權重和到達的點

一直做到Queue清空, 但一直吃NA 40% 後面的三組測資都過不了

改成用DFS暴力嘗試每一種路徑後就AC

問一下怎樣的情況下才能知道可以用Priorty Queue 怎麼要用DFS暴力法, 謝謝～

話說題目沒提到每組點之間可能會給複數條edge的情況...

 
#30701: Re: 關於這一題的解法


vic20050418@gmail.com (Wen Vic)

學校 : 國立臺灣科技大學
編號 : 153262
來源 : [114.136.159.95]
最後登入時間 ：
2023-07-29 13:10:41
d908. 4. 最佳路徑 -- 99學年度北基區資訊學科能力競賽 | From: [223.137.51.103] | 發表日期 : 2022-06-07 20:23

不好意思, 想問一下高手們這個題目中

一開始我用 Priority Queue

Queue裡面的排序方式是 到達其他點的權重

因此作為下一次展開的選擇都是 Queue裡面的最大權重和到達的點

一直做到Queue清空, 但一直吃NA 40% 後面的三組測資都過不了

改成用DFS暴力嘗試每一種路徑後就AC

問一下怎樣的情況下才能知道可以用Priorty Queue 怎麼要用DFS暴力法, 謝謝～

話說題目沒提到每組點之間可能會給複數條edge的情況...

這題反著考 平時都考最短路徑
BFS比較輕鬆吧 設個dis陣列 數值最後會越滾越大 最後迴圈去找Maximum
大概40 line 左右解決 我覺得這題比當年前面幾題還簡單XD

 
ZeroJudge Forum