poj1860Bellman_Ford算法

 1 #include
 2 #include<string.h>
 3 
 4 struct Node{
 5     int u,v;    // 起点，终点
 6     double r,c;
 7 };
 8 
 9 Node edge[221]; bool flg;
10 double dis[110];
11 
12 int nodenum, edgenum, source,t;    // 结点数，边数，源点,起始值,总边数
13 double V;
14 
15 void relax(int u,int v,double r,double c)   //*用double 
16 {
17     if(dis[v]<(dis[u]-c)*r);
18         dis[v]=(dis[u]-c)*r;
19 }
20 
21 bool Bellman_Ford()
22 {
23     int i,j,k;
24     for(i=1;i<=nodenum;i++)
25         dis[i]=0;
26     dis[source]=V;
27 
28     for(i=1;i<=nodenum-1;i++)
29     {
30         for(j=1;j<=t;j++)                   //*注意是总边数
31         {
32             relax(edge[j].u,edge[j].v,edge[j].r,edge[j].c);
33         }
34         /*flg=false;   //优化做法
35         for(j=1;j<=t;j++)
36         {
37             if(dis[edge[j].v] <(dis[edge[j].u]-edge[j].c)*edge[j].r)//求最大
38             {
39                 //flg=true;
40                 dis[edge[j].v]=(dis[edge[j].u]-edge[j].c)*edge[j].r;
41             }
42         }
43         if(!flg) return false;*/
44     }
45     //judge
46 
47     for(i=1;i<=t;i++)
48     {
49         if(dis[edge[i].v]<(dis[edge[i].u]-edge[i].c)*edge[i].r)
50             return true;
51     }
52     return false;
53 }
54 
55 
56 int main()
57 {
58     int i,j,k;
59     while(scanf("%d %d %d %lf",&nodenum,&edgenum,&source,&V)!=EOF)
60     {
61         t=1;
62         for(i=1;i<=edgenum;i++)
63         {
64             scanf("%d %d %lf %lf",&edge[t].u,&edge[t].v,&edge[t].r,&edge[t].c);
65             t++;
66             edge[t].u=edge[t-1].v,edge[t].v=edge[t-1].u;
67             scanf("%lf %lf",&edge[t].r,&edge[t].c);
68             t++;
69         }
70         t--;                    //总边数值
71         if(Bellman_Ford()==true)
72             printf("YES\n");
73         else
74             printf("NO\n");
75     }
76     return 0;
77 }