洛谷 P2868 [USACO07DEC]观光奶牛Sightseeing Cows

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<queue>
 4 #include<cstring>
 5 #define eps (1e-8)
 6 using namespace std;
 7 struct E
 8 {
 9     int to,nxt,dd;
10     double d;
11 }e[5010];
12 int f1[1010],ne;
13 int n,m,F[1010];
14 int num[1010],inq[1010],vis[1010];
15 double dis[1010];
16 bool fl;
17 queue<int> q;
18 void spfa(int u)
19 {
20     int k,v;
21     while(!q.empty())    q.pop();
22     dis[u]=0;vis[u]=inq[u]=1;num[u]=1;
23     q.push(u);
24     while(!q.empty())
25     {
26         u=q.front();q.pop();inq[u]=0;
27         for(k=f1[u];k;k=e[k].nxt)
28         {
29             v=e[k].to;
30             if(dis[v]>dis[u]+e[k].d)
31             {
32                 dis[v]=dis[u]+e[k].d;
33                 if(!inq[v])
34                 {
35                     q.push(v);inq[v]=vis[v]=1;num[v]++;
36                     if(num[v]>=n)    {fl=1;return;}
37                 }
38             }
39         }
40     }
41 }
42 int main()
43 {
44     int i,k,a,b,t;double l,r,mid;
45     scanf("%d%d",&n,&m);
46     for(i=1;i<=n;i++)    scanf("%d",&F[i]);
47     for(i=1;i<=m;i++)
48     {
49         scanf("%d%d%d",&a,&b,&t);
50         e[++ne].to=b;e[ne].nxt=f1[a];f1[a]=ne;e[ne].dd=t;
51     }
52     l=0;r=1000;
53     while(r-l>eps)
54     {
55         mid=l+(r-l)/2;
56         for(i=1;i<=n;i++)
57         {
58             for(k=f1[i];k;k=e[k].nxt)
59             {
60                 e[k].d=mid*e[k].dd-F[i];
61             }
62         }
63         fl=0;
64         for(i=1;i<=n;i++)    dis[i]=0x3f3f3f3f;
65         memset(vis,0,sizeof(vis));
66         memset(inq,0,sizeof(inq));
67         memset(num,0,sizeof(num));
68         for(i=1;i<=n;i++)
69             if(!fl&&!vis[i])
70                 spfa(i);
71         fl?l=mid:r=mid;
72     }
73     printf("%.2lf",l-0.0005);
74     return 0;
75 }