poj3411Paid Roads(dfs)

想偷点懒用矩阵存一直WA 后来看讨论说有重边改为邻接表这题边可能走了不止一次我设的最多两次可过
 1 #include <iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<stdlib.h>
 6 using namespace std;
 7 #define INF 0xfffffff
 8 struct node
 9 {
10     int u,v,w1,w2,d,next;
11 }ed[22];
12 int head[12];
13 int n,m,p[12][12],ans;
14 int vis[12],t;
15 void init()
16 {
17     t = 0;
18     memset(head,-1,sizeof(head));
19 }
20 void add(int u,int v,int w1,int w2,int d)
21 {
22     ed[t].u = u;
23     ed[t].v = v;
24     ed[t].w1 = w1;
25     ed[t].w2 = w2;
26     ed[t].d = d;
27     ed[t].next = head[u];
28     head[u] = t++;
29 }
30 void dfs(int u,int sum)
31 {
32     int i,s=sum;
33     if(sum>ans)
34     return ;
35     if(u==n)
36     {
37         ans = sum;
38         return ;
39     }
40     for(i = head[u] ; i!= -1; i = ed[i].next)
41     {
42         int v = ed[i].v;
43         int tt = vis[v];
44         if(p[u][v]<3)
45         {
46             vis[v] = 1;
47             p[u][v]++;
48             if(ed[i].d==u||ed[i].d==i||vis[ed[i].d])
49             {
50                 sum+=min(ed[i].w1,ed[i].w2);
51             }
52             else
53             {
54                 sum+=ed[i].w2;
55             }
56             dfs(v,sum);
57             sum = s;
58             p[u][v]--;
59             vis[v] = tt;
60         }
61     }
62 }
63 int main()
64 {
65     int a,b,c,pp,r;
66     while(scanf("%d%d",&n,&m)!=EOF)
67     {
68         init();
69         memset(vis,0,sizeof(vis));
70         memset(p,0,sizeof(p));
71         ans = INF;
72         while(m--)
73         {
74             scanf("%d%d%d%d%d",&a,&b,&c,&pp,&r);
75             add(a,b,pp,r,c);
76         }
77         vis[1] = 1;
78         dfs(1,0);
79         if(ans!=INF)
80         printf("%d
",ans);
81         else
82         puts("impossible");
83     }
84     return 0;
85 }
View Code