hdu 2437(dfs)

タイトルリンク:http://acm.hdu.edu.cn/showproblem.php?pid=2437
考え方:ある点に到達したときの経路長mod kの最短経路長を2次元配列で記録するだけで、残数が同じであれば最小値を更新します.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