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

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

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

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

因?yàn)閱?wèn)題描述當(dāng)中，有要求的天數(shù)，和花費(fèi)的錢(qián)數(shù)，那么這個(gè)方程到底怎么表示呢！

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

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

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

  

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

View Code