POJ 1860 Currency Exchange(SPFA)

제목 링크
SPFA는 과연 기능이 강력하다, 1Y.

 1 #include <cstdio>

 2 #include <cstring>

 3 #include <cmath>

 4 #include <queue>

 5 #include <iostream>

 6 using namespace std;

 7 #define N 10000000

 8 double p1[101][101],p2[101][101],d[101],v;

 9 int n;

10 int spfa(int str)

11 {

12     int in[101],u,i;

13     memset(in,0,sizeof(in));

14     for(i = 1;i <= n;i ++)

15     {

16         d[i] = 0;

17     }

18     d[str] = v;

19     queue<int> que;

20     que.push(str);

21     in[str] = 1;

22     while(!que.empty())

23     {

24         u = que.front();

25         in[u] = 0;

26         que.pop();

27         for(i = 1;i <= n;i ++)

28         {

29             if(p1[u][i] != N&&d[i] < (d[u]-p2[u][i])*p1[u][i])

30             {

31                 d[i] = (d[u]-p2[u][i])*p1[u][i];

32                 if(!in[i])

33                 {

34                     in[i] = 1;

35                     que.push(i);

36                 }

37             }

38         }

39         if(d[str] > v)

40         return 1;

41     }

42     return 0;

43 }

44 int main()

45 {

46     int m,str,sv,ev,i,j;

47     double w1,w2,w3,w4;

48     scanf("%d%d%d%lf",&n,&m,&str,&v);

49     for(i = 1;i <= n;i ++)

50     {

51         for(j = 1;j <= n;j ++)

52         {

53             p1[i][j] = N;

54             p2[i][j] = N;

55         }

56     }

57     for(i = 1;i <= m;i ++)

58     {

59         scanf("%d%d%lf%lf%lf%lf",&sv,&ev,&w1,&w2,&w3,&w4);

60         p1[sv][ev] = w1;

61         p2[sv][ev] = w2;

62         p1[ev][sv] = w3;

63         p2[ev][sv] = w4;

64     }

65     if(spfa(str))printf("YES
");

66     else printf("NO
");

67 }