hdu 2437(dfs)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2437

思路:只需用一个二维数组记录到达某点时路径长度mod k的最短路径长度，如果余数相同，就更新最小值。dfs暴搜即可。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<vector>
 6 using namespace std;
 7 #define MAXN 1111
 8 #define inf 1<<30
 9 
10 struct Edge{
11     int v,w;
12     Edge(int vv,int ww):v(vv),w(ww){};
13 };
14 
15 int dist[MAXN][MAXN];//走到点i，路程长度mod k余数为j的最短路程
16 char num[MAXN];
17 int n,m,s,k,min_len,pos;
18 
19 vector<vector<Edge> >G;
20 
21 void dfs(int u,int len)
22 {
23     if(len%k==0&&num[u]=='P'){
24         if(len<min_len){
25             min_len=len,pos=u;
26         }else if(len==min_len){
27             pos=min(pos,u);
28         }
29         return ;
30     }
31     for(int i=0;i<G[u].size();i++){
32         int v=G[u][i].v,w=G[u][i].w;
33         if(dist[v][(len+w)%k]==-1||dist[v][(len+w)%k]>(len+w)){
34             dist[v][(len+w)%k]=len+w;
35             dfs(v,len+w);
36         }
37     }
38 }
39 
40 
41 int main()
42 {
43     int _case,u,v,w,t=1;
44     scanf("%d",&_case);
45     while(_case--){
46         scanf("%d%d%d%d",&n,&m,&s,&k);
47         scanf("%s",num+1);
48         G.clear();
49         G.resize(n+2);
50         while(m--){
51             scanf("%d%d%d",&u,&v,&w);
52             G[u].push_back(Edge(v,w));
53         }
54         memset(dist,-1,sizeof(dist));
55         min_len=inf;
56         dfs(s,0);
57         if(min_len==inf){
58             printf("Case %d: -1 -1
",t++);
59         }else 
60             printf("Case %d: %d %d
",t++,min_len,pos);
61     }
62     return 0;
63 }
64 
65 
66         
67 
68 
69

View Code