1樓：
補充：我是這道題目的出題人，下面是我提交給年鑑的解題報告。這道題目資料出了比較嚴重的問題，當年包括我和驗題人在內都沒有發現，在這裡也給選手們道個歉。
==分割線==
本題考查同學們對最短路以及搜尋演算法的掌握程度。
本題是一道典型的最短路模型的題目，但是由於所走的路徑有限制，若將圖根據不同的狀態拆點，則點數將是指數級的，顯然不能解決N比較大的情況。只有當N比較小的時候可以用(u, set)來表示到達u且以後不能到達文化編號為set集合中的編號的最短路。當N比較大的時候，比較不錯的做法是利用經典的搜尋演算法來計算最短路，這也是標程的做法。
首先，可以二分最優解，設為X，然後用A* search algorithm來驗證X是否為乙個可行解。A星演算法的估價函式選取很重要。比如我們可以選擇當前到達的點u到終點T的最短距離作為估價函式，但是顯然因為它沒有利用已經訪問到的節點的資訊，並不是乙個好的估價函式。
乙個好的估價函式可以是，從當前節點u到終點T的不經過與已經到達的國家相衝突的國家的最短路的長度。利用二分和A星剪枝，程式可以很快的跑出答案。
NOIp普及組應掌握什麼演算法？
列舉演算法 模擬演算法 動態規劃必須掌握，這三種演算法基本上每年都會有一題，列舉和模擬掌握了基本拿獎就沒問題了，動態規劃，很難掌握 講真，會模擬 暴力，就保省二了。再會點騙分技巧，省一都有了 模擬深搜 剪枝簡單一點的dp 騙分 暴力，模擬，位運算，深搜 剪枝，精通這幾項，大概省二就有了 弱一點的省估...
如何評價NOIP2017普及組複賽？
Conservation NOIP 2017那時我資訊學才學了三個月，結果初賽60多分都能過 當時把老師都嚇得不輕，因為分數線只有40多分 本來想著複賽會不會爆零，結果看到題目那一刻突然想笑 T1，T2不講了，做不出來的估計都是沒看清題意 比如我校有個dalao，T1居然用了浮點數乘法，差點就沒了省...
如何評價NOIP2017普及組複賽score題目成績更新？
Hongzy 當時一開始把檔案操作注釋掉了，手輸測試樣例，發現樣例二答案算出來少1 應該不是眼花 覺得第一題可能坑就在精度，就果斷改成先除後乘.最後對了.不過看別人直接用小數乘也是對的. 利益相關 GD普及組蒟蒻選手 我記得在考試的時候，如果直接乘零點幾的話，樣例都是過不了的。我想大家看到出了這樣的...