LightOj_1287 Where to Run

 1 #include <cmath>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <ctime>
 6 #include <set>
 7 #include <map>
 8 #include <list>
 9 #include <queue>
10 #include <string>
11 #include <vector>
12 #include <fstream>
13 #include <iterator>
14 #include <iostream>
15 #include <algorithm>
16 using namespace std;
17 #define LL long long
18 #define INF 0x3f3f3f3f
19 #define MOD 1000000007
20 #define eps 1e-7
21 #define MAXN 110
22 #define MAXM 16
23 #define dd cout<<"debug"<<endl
24 #define p(x) printf("%d\n", x)
25 #define pd(x) printf("%.7lf\n", x)
26 #define k(x) printf("Case %d: ", ++x)
27 #define s(x) scanf("%d", &x)
28 #define sd(x) scanf("%lf", &x)
29 #define mes(x, d) memset(x, d, sizeof(x))
30 #define f(i, x) for(i = 0; i < x; i ++)
31 int n, m;
32 int w[MAXN][MAXN];
33 double E[MAXM][1 << MAXM];
34 bool vis[MAXM][1 << MAXM];
35 
36 bool dfs(int staues, int root)
37 {
38     if(staues == (1 << n) - 1)
39     {
40         E[root][staues] = 0;
41         return true;
42     }
43     if(vis[root][staues]) return E[root][staues] > 0;
44     vis[root][staues] = true;
45     E[root][staues] = 5;
46     int cnt = 0, sttemp;
47     int i;
48     f(i, n)
49         if(!(staues & (1 << i)) && w[root][i] != INF && dfs((staues | (1 << i)), i))
50         {
51             sttemp = staues | (1 << i);
52             cnt ++;
53             E[root][staues] += w[root][i] + E[i][sttemp];
54         }
55     if(!cnt)
56     {
57         E[root][staues] = 0;
58         return false;
59     }
60     E[root][staues] /= cnt;
61     return true;
62 }
63 
64 int main()
65 {
66     int T;
67     int kcase = 0;
68     s(T);
69     while(T --)
70     {
71         int u, v;
72         int ww;
73         s(n), s(m);
74         mes(w, 0x3f);
75         mes(vis, false);
76         int i;
77         f(i, m)
78         {
79             s(u), s(v), s(ww);
80             w[u][v] = w[v][u] = ww;
81         }
82         dfs(1, 0);
83         k(kcase), pd(E[0][1]);
84     }
85     return 0;
86 }