达内杯--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