USACO Fence Loops

USACO给出的解答是先建图，然后转化成最短路问题解，并给出了优化方法：删除搜过的边。
实际上对于这题并不需要如此复杂，加之数据量很小，只需要几次DFS就可以了，代码很简短。评测显示所有测试数据都在～0.00s内出解
当然，USACO给出的建模思路还是很值得学习的。

使用DFS的代码：

C语言: 高亮代码由发芽网提供

01 #include <stdio.h>
02 #include <stdlib.h>
03 #include <string.h>
04
05 int N;
06 int len[101];
07
08 short side[101][101] = {};  //表示两个边的相互位置关系，用0，1区分一条线段两侧的边
09 int raw[101][2][10] = {};   //分两侧的边集数组
10 void init()
11 {
12     int i,j,t1,t2,s;
13     scanf("%d",&N);
14     for(i = 1;i <= N;i ++)
15     {
16         scanf("%d",&s);
17         scanf("%d %d %d",&len[s],&t1,&t2);
18         for(j = 0;j < t1;j ++)
19         {
20             scanf("%d",&raw[s][0][j]);
21             side[s][raw[s][0][j]] = 0;
22         }
23         for(j = 0;j < t2;j ++)
24         {
25             scanf("%d",&raw[s][1][j]);
26             side[s][raw[s][1][j]] = 1;
27         }
28     }
29 }
30
31 int visit[101];
32 int min;
33 int source;   //DFS开始时刻的边
34
35 void dfs(int now,int p,int s)   //p,累计长度  s,下一条边应该在now的哪个方向上
36 {
37     int i;
38     if(p >= min)    return;   //所谓剪枝
39     if(now == source && p != 0)
40     {
41         min = p;
42         /*printf("Found:");
43         for(i = 0;i < 101;i ++)
44             if(visit[i])
45             {
46                 printf("%d ",i);
47             }
48         printf("\n");*/
49         return;
50     }
51     for(i = 0;i < 8 && raw[now][s][i] != 0;i ++)
52     {
53         if(!visit[raw[now][s][i]])
54         {
55             visit[raw[now][s][i]] = 1;
56             dfs(raw[now][s][i],p + len[now],1 - side[raw[now][s][i]][now]);
57             visit[raw[now][s][i]] = 0;
58         }
59     }
60 }
61
62 void solve()
63 {
64     min = 255 * 100 + 100;
65     for(source = 1;source <= N;source ++)  //对每条边进行一次DFS
66     {
67         memset(visit,0,sizeof(visit));
68         dfs(source,0,0);
69     }
70     printf("%d\n",min);
71 }
72
73 int main()
74 {
75     freopen("fence6.in","r",stdin);
76     freopen("fence6.out","w",stdout);
77     init();
78     solve();
79     return 0;
80 }