poj 3411 Paid Roads

 1 /*
    http://poj.org/problem?id=3411

 2 题目意思：
 3 从a到b有两种付费方式 1：在a之前已经访问了c（不一定是刚访问），付费p；2：a直接到b 付费r；
 4 求 1到n 的最小费用（注意有的点可以访问多次）
 5 
 6 解题思路：dfs ，题目的关键是一个点可能被访问多次，一条边也可能被访问多次
 7 某一个点是否访问过可以用f[i]标记，f[i]>0表示访问过了
 8 其次还有一点很重要的，就是每个城市最多经过3次（网上说的“闸数”）就可以跳出循环了
 9 （一开始以为每条边只会访问一次，wa）
10 
11 */
12 #include<stdio.h>
13 #include<string.h>
14 #define N 15
15 #define max 999999
16 struct node
17 {
18     
19     int b;
20     int c;
21     int p;
22     int r;
23     int next;
24 }node[N];
25 int n,m;
26 int num;
27 int next[N];
28 
29 int  ans;
30 int f[N];
31 void  add(int a,int b,int c,int p,int r)
32 {
33     node[num].b=b;
34     node[num].c=c;
35     node[num].p=p;
36     node[num].r=r;
37     node[num].next=next[a];
38     next[a]=num++;
39 }
40 void DFS(int x,int sum)
41 {
42      if(f[x]>=4)return ;
43     if(x==n)
44     {
45 
46         if(ans>sum)ans=sum;
47         return ;
48     }
49 
50     for(int i=next[x];i!=-1;i=node[i].next)
51     {
52         
53           
54            f[node[i].b]++;
55           if(f[node[i].c]!=0)
56          {
57 
58             DFS(node[i].b,sum+node[i].p);
59 
60 
61          }
62 
63           DFS(node[i].b,sum+node[i].r);
64           f[node[i].b]--;
65          
66     }
67 
68 }
69 int main()
70 {
71     int a,b,c,p,r;
72     while(scanf("%d%d",&n,&m)!=EOF)
73     {
74         num=0;
75         ans=max;
76         memset(next,-1,sizeof(next));
77         
78         memset(f,0,sizeof(f));
79         for(int i=0;i<m;i++)
80         {
81             scanf("%d%d%d%d%d",&a,&b,&c,&p,&r);
82             add(a,b,c,p,r);
83         }
84         f[1]=1;
85         DFS(1,0);
86         if(ans==max)printf("impossible\n");
87         else
88         printf("%d\n",ans);
89 
90     }
91 }