poj 3411 Paid Roads很水的DFS

题意：给你N　　城市和M条道路，每条道路要付的钱，但是如果你在这个道路上你可以付其他道路的钱（跟走到的时候去的话不一样），问你从1走到N最少话费是多少。

直接DFS搜。

代码：

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <iostream>
 4 #include <algorithm>
 5 #include <stdlib.h>
 6 #include <vector>
 7 #include <queue>
 8 #include <stack>
 9 #define loop(s,i,n) for(i = s;i < n;i++)
10 #define cl(a,b) memset(a,b,sizeof(a))
11 const int maxn = 521;
12 const int inf = 99999999;
13 using namespace std;
14 struct node
15 {
16     int u,v,c,r,p;
17 };
18 vector <struct node >g[15];
19 int vis[15];
20 int ans;
21 int n,m;
22 void dfs(int u,int val)
23 {
24     vis[u]++;
25     if(u == n)
26     {
27         if(ans > val)
28         ans = val;
29         return ;
30     }
31 
32     if(ans < val)
33     return;
34 
35 
36 
37     int i;
38 
39     for(i = 0;i < g[u].size();i++)
40     {
41         int v;
42         v = g[u][i].v;
43         int c;
44         c = g[u][i].c;
45         if(vis[v] <= 3)
46         {
47             int min;
48             min = inf;
49             if(vis[c] && min > g[u][i].p)
50             min = g[u][i].p;
51             if(min > g[u][i].r)
52             min = g[u][i].r;
53 
54             dfs(v,val+min);
55             vis[v]--;
56         }
57     }
58 
59 }
60 
61 int main()
62 {
63     int u,v,t,p,r;
64     while(~scanf("%d %d",&n,&m))
65     {
66         int i,j;
67         memset(vis,0,sizeof(vis));
68         for(i = 1;i <= n;i++)
69         g[i].clear();
70 
71         while(m--)
72         {
73             scanf("%d%d%d%d%d",&u,&v,&t,&p,&r);
74             g[u].push_back((struct node){u,v,t,r,p});
75         }
76         ans = inf;
77         dfs(1,0);
78         if(ans != inf)
79         cout<<ans<<endl;
80         else
81         puts("impossible");
82     }
83     return 0;
84 }

View Code