達內(nèi)杯--H 技術(shù)員BangFu 

 這題的確是一道好題，很好的將狀態(tài)dp以及圖論的最短路徑，這里上面的權(quán)值表示的花費的錢，另外還有很多約束問題，

 首先大體描述下這道題，就是一個技術(shù)員，遍歷N個節(jié)點，首先他一開始在0號節(jié)點，且是星期一，然后遍歷1..N-1 編號的節(jié)點，這里要求每個節(jié)點只能走一次，而且必須每個節(jié)點都得走到，最后還要回到0號節(jié)點，而且從一個定點到另一個頂點是要花費p天的時間，還要要一定的錢，而且在每個節(jié)點也至少得待一天的時間，最后的最后，要我們解決的問題是，首先判定他是否能夠每個節(jié)點都能走到，另外，如果能又是否能在星期六或星期天到，若是，那么我們至少得花多少錢呢！

  問題已經(jīng)很清晰了，現(xiàn)在的問題就是如何求了，按照我開始的思路，首先判定這是否是一個遍歷所有節(jié)點的回路，然后既然這是一個狀態(tài)dp的問題，那么肯定是涉及到狀態(tài)的改變的，那么狀態(tài)是什么呢，這里就是走過的節(jié)點，可以作為狀態(tài)，如果已經(jīng)走過，那么為1，否則為0，那么N個節(jié)點可以表示成一個二進制串，然后相對應(yīng)的十進制值就是狀態(tài)數(shù)，如上，我們?nèi)绾闻袛酄顟B(tài)的合法性，這里就是走過的節(jié)點就不要回去了，所以就很好判斷了，也就是說每一位只能置1一次，好，搞過之后，我們在找狀態(tài)方程，因為這里好像很隱藏，

因為問題描述當(dāng)中，有要求的天數(shù)，和花費的錢數(shù)，那么這個方程到底怎么表示呢！

 這里設(shè)dp[state][des][d]  這個方程的意思就是狀態(tài)為state時，且到達了des節(jié)點，且此時是星期d ，另外這個值就是達到這點所花費的錢   0<=state<2^N,1<=des<=N-1,0<=d<7

   然后就是初始化問題，dp[0][0][0]=inf,dp[1][0][0]=0,然后就是用bfs遍歷找出求最短路勁了，這里最短路勁也好求，首先在輸入的時候，建立鄰接表，bfs的用隊列維護，這里就如上所述，所涉及的要保存的信息很多，于是我們想到結(jié)構(gòu)體，用結(jié)構(gòu)體來表示節(jié)點以及邊，這樣，這個過程就很好辦了，當(dāng)然我們知道bfs的過程中，還有一個visit的，這里也需要建立類似的標(biāo)記，這里要和dp有同樣的大小，

 這樣搞過之后，最后就很好辦了，首先dp[2^N-1][1....N][D] ，循環(huán)遍歷在目標(biāo)1....N個節(jié)點中看看有沒到0號節(jié)點的，兩個fou循環(huán)，找出最小值，同時判斷是否能夠在星期六和星期天道，這些都很好辦了，，接下來就可以去是實現(xiàn)了，，就是苦力活了，，有許多的細節(jié)，要考慮全面！

  

   下面的代碼就是寫給自己看的，成功AC！
    

View Code