#15115: 關於這一題的解法


rollfc (胖胖貓)

School : 國立清華大學
ID : 81012
IP address : [36.229.45.40]
Last Login :
2024-07-15 00:12:15
d908. 4. 最佳路徑 -- 99學年度北基區資訊學科能力競賽 | From: [140.113.208.181] | Post Date : 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)

School : 國立臺灣科技大學
ID : 153262
IP address : [114.136.159.95]
Last Login :
2023-07-29 13:10:41
d908. 4. 最佳路徑 -- 99學年度北基區資訊學科能力競賽 | From: [223.137.51.103] | Post Date : 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