達內杯--H 技術員BangFu
這題的確是一道好題，很好的將狀態dp以及圖論的最短路徑，這里上面的權值表示的花費的錢，另外還有很多約束問題，
首先大體描述下這道題，就是一個技術員，遍歷N個節點，首先他一開始在0號節點，且是星期一，然后遍歷1..N-1 編號的節點，這里要求每個節點只能走一次，而且必須每個節點都得走到，最后還要回到0號節點，而且從一個定點到另一個頂點是要花費p天的時間，還要要一定的錢，而且在每個節點也至少得待一天的時間，最后的最后，要我們解決的問題是，首先判定他是否能夠每個節點都能走到，另外，如果能又是否能在星期六或星期天到，若是，那么我們至少得花多少錢呢！
問題已經很清晰了，現在的問題就是如何求了，按照我開始的思路，首先判定這是否是一個遍歷所有節點的回路，然后既然這是一個狀態dp的問題，那么肯定是涉及到狀態的改變的，那么狀態是什么呢，這里就是走過的節點，可以作為狀態，如果已經走過，那么為1，否則為0，那么N個節點可以表示成一個二進制串，然后相對應的十進制值就是狀態數，如上，我們如何判斷狀態的合法性，這里就是走過的節點就不要回去了，所以就很好判斷了，也就是說每一位只能置1一次，好，搞過之后，我們在找狀態方程，因為這里好像很隱藏，
因為問題描述當中，有要求的天數，和花費的錢數，那么這個方程到底怎么表示呢！
這里設dp[state][des][d] 這個方程的意思就是狀態為state時，且到達了des節點，且此時是星期d ，另外這個值就是達到這點所花費的錢 0<=state<2^N,1<=des<=N-1,0<=d<7
然后就是初始化問題，dp[0][0][0]=inf,dp[1][0][0]=0,然后就是用bfs遍歷找出求最短路勁了，這里最短路勁也好求，首先在輸入的時候，建立鄰接表，bfs的用隊列維護，這里就如上所述，所涉及的要保存的信息很多，于是我們想到結構體，用結構體來表示節點以及邊，這樣，這個過程就很好辦了，當然我們知道bfs的過程中，還有一個visit的，這里也需要建立類似的標記，這里要和dp有同樣的大小，
這樣搞過之后，最后就很好辦了，首先dp[2^N-1][1....N][D] ，循環遍歷在目標1....N個節點中看看有沒到0號節點的，兩個fou循環，找出最小值，同時判斷是否能夠在星期六和星期天道，這些都很好辦了，，接下來就可以去是實現了，，就是苦力活了，，有許多的細節，要考慮全面！
下面的代碼就是寫給自己看的，成功AC！
View Code
1
#include<iostream>
2#include<vector>
3#include<queue>
4#include<algorithm>
5#define inf 0x7fffffff
6using namespace std;
7struct edge
8
{
9
int y,p,t; //含義如題所述
10
};
11struct node
12{
13 int s,n,d; //s表示當前狀態，n表示節點標號，d表示經過的天數
14};
15vector<edge> num[11];
16int dp[1<<10][11][7];
17int visit[1<<10][11][7];
18queue<node> qu;
19int N,M;
20void sloveinput()
21{
22 //初始化
23 for(int i=0;i<(1<<N);i++)
24 for(int j=0;j<N;j++)
25 for(int k=0;k<7;k++)
26
{
27 dp[i][j][k]=inf;
28 visit[i][j][k]=0;
29
}
30 for(int i=0;i<N;i++)
31 num[i].clear();
32 edge tmp;
33 for(int i=0;i<M;i++)
34 {
35 int a;
36 cin>>a>>tmp.y>>tmp.p>>tmp.t;
37 num[a].push_back(tmp);
38 }
39 //鄰接表以建立好
40}
41void slovedp()
42{
43 //這個函數就是要求dp[][][]里面能求的值，要用隊列
44 node start;
45 edge tmp;
46 start.s=1;start.n=0;start.d=0;
47 //
48 tmp.y=0;tmp.p=0;tmp.t=0;
49 //這里從0號節點開始，00001 所以狀態s為1，但是節點y為0，當然p，和t為0
50 // qu.clear();
51 dp[1][0][0]=0;
52 visit[1][0][0]=1;
53 qu.push(start);
54 while(!qu.empty()) //開始bfs嘍
55 {
56 node tp=qu.front();
57 qu.pop();
58 for(int i=0;i<num[tp.n].size();i++) //在這些臨邊遍歷
59 {
60 if(!(tp.s&(1<<num[tp.n][i].y)))
61 //這說明以前這個節點還是沒有走過的，那么可擴展，
62 //這里就是判定合法狀態的條件，狀態dp一般到要這樣
63 {
64 //建立節點保存，并入隊列，
65 node node1;
66 node1.s=tp.s|(1<<num[tp.n][i].y);
67 node1.n=num[tp.n][i].y;
68 node1.d=(tp.d+num[tp.n][i].t+1)%7;
69 //到這里后，如何判定入棧呢
70 if(dp[tp.s][tp.n][tp.d]+num[tp.n][i].p<dp[node1.s][node1.n][node1.d])
71 //如果通過上一個狀態 花費加上到當前節點的花費小于 當前狀態的花費，則擴充，入棧，//這里是重要的地方，狀態轉移方程
72 {
73 dp[node1.s][node1.n][node1.d]=dp[tp.s][tp.n][tp.d]+num[tp.n][i].p; //更新吧
74 if(!visit[node1.s][node1.n][node1.d])
75 {
76 visit[node1.s][node1.n][node1.d]=1;
77 qu.push(node1);
78 }
79 }
80 }
81 }
82 }
83}
84void sloveans()
85{
86 //這個收尾就很簡單嘍
87 int end=(1<<N)-1;
88 int flag1=0,flag2=0;
89 int ans=inf;
90 for(int i=1;i<=N-1;i++) //遍歷
91 for(int j=0;j<num[i].size();j++)
92 {
93 if(num[i][j].y==0) //說明有回到0節點的
94 {
95 for(int dd=0;dd<7;dd++) //判定是否能在周六或周日到
96 {
97 if(dp[end][i][dd]<inf)
98 //說明有成功到達0節點的，且遍歷了所有節點,這里一開始寫成里 dp[end][num[i][j].y][dd]<inf，細節問題一定要注意啊
99 {
100 flag1=1;
101 //再是第二個條件，看是否能在周六或周日到達
102 if(((dd+num[i][j].t)%7)>=5&&ans>dp[end][i][dd]+num[i][j].p)
103 //這里把星期一去掉，默認從0，那么經過t天后，如果是5,6，就說明了是能在星期六和星期日到達的
104 //并且找到滿足的最小花費值
105 {
106 flag2=1;
107 ans=dp[end][i][dd]+num[i][j].p;
108 }
109 }
110 }
111 }
112 }
113 if(!flag1) cout<<"It's not my thing!"<<endl;
114 else if(!flag2) cout<<"Oh, My god!"<<endl;
115 else cout<<ans<<endl;
116}
117int main()
118{
119 while(cin>>N>>M)
120 {
121 sloveinput();
122 slovedp();
123 sloveans();
124 }
125}
126