HDU2437 2008 Asia Chengdu Regional Contest Online记忆化搜索+剪枝

#include<bits/stdc++.h> using namespace std; /*记录到达这一点%k的最小距离，如果当前距离》最小距离，就更新一下   算是记录状态的搜索，状态的描述方便剪枝*/    typedef long long ll; const int maxn = 1010; const ll INF = 1e18; struct edge{ int to; int cost; edge(int a,int b):to(a),cost(b){ } edge(){ } }; vector<edge> gra[maxn]; ll dp[maxn][maxn]; ll y = INF,z = -1; int n,m,s,k; bool torp[maxn]; int dfs(int pos,ll cost,int mod){     //printf("%d %d %d\n",pos,cost,mod); if (dp[pos][mod] <= cost)return 0;//大于到这个地方的最小值，剪      dp[pos][mod] = cost;  if (cost > y) return 0;//大于当前最小值，剪  if (torp[pos] == 1 && mod == 0){//是可以整出k地达到目的地，更新最值，剪  if (cost < y){ y = cost; z = pos; } else if (cost == y){ if (pos < z){ z = pos; } } return 0; }  for(int i = 0; i < gra[pos].size(); i++){ dfs(gra[pos][i].to,gra[pos][i].cost + cost,(mod + gra[pos][i].cost) % k); } return 0; } int main() {     int t; scanf("%d",&t); for(int test = 1; test <= t; test++){ scanf("%d %d %d %d",&n,&m,&s,&k); char s1[maxn]; scanf("%s",s1); for(int i = 0; i < n; i++){ if (s1[i] == 'T') torp[i + 1] = 0; else torp[i + 1] = 1; gra[i + 1].clear(); } for(int i = 1; i <= m; i++){ int from,to,cost; scanf("%d %d %d" ,&from,&to,&cost); gra[from].push_back(edge(to,cost)); } for(int i = 1; i <= n; i++) for(int j = 0; j <=  k; j++)    dp[i][j] = INF; y = INF; z = -1; dfs(s,0,0); if (y == INF) y = -1; printf("Case %d: %I64d %d\n",test,y,z) ; } return 0;

}

/*

从T出发走到P，要求最短的，%k = 0的路径终点和长度

如果有一样长的，取编号小的终点

开始没懂题意，以为是最短路

看了题解之后直到原来直接DFS就可以了

这题卡了if (dp[pos][mod] <= cost)return 0;//大于到这个地方的最小值，剪

这个剪枝，其实是记忆化搜索，如果直接暴力，也要记录当前的总和，然后一直搜

在某个点处，怎么知道现在已经不用搜了？

1.当前的总和已经超过最值

2.以前达到这个点的时候总和比现在的小

3.所以只要记录状态就可以了，加个剪枝轻松过，这个剪枝的作用是防止重复一种状态。

其实状态应该dp[第几个点][当前经过的距离][mod k的值] ，这里把经过的距离当作状态的标记，因为一个时间只用存一个当前最短距离就可以了……

复杂度上，状态数是1000*1000，之后的复杂度就不好分析了……

碰到这种题也只有试试看DFS能不能过了吧

*/