Wormholes

Bellman_ford : 判断是否有负权回路 282MS

View Code

 1 #include<iostream>
 2 using namespace std ;
 3 #define INF 1>>28
 4 #define N 6000
 5 struct node
 6 {
 7     int a ;
 8     int b ;
 9     int c ;
10 }e[N] ;
11 int n, m, w, num ;
12 int bellman_ford()
13 {
14     int dis[N] ;
15     for(int i=1; i<=n; i++)
16     dis[i] = INF ;
17     dis[1] = 0 ;//以这个为源点
18     for(int i=1; i<n; i++)//松弛n-1次就必定找出最短路径
19     {
20         for(int j=1; j<num; j++)
21         if(dis[e[j].b]>dis[e[j].a]+e[j].c)
22         dis[e[j].b] = dis[e[j].a] + e[j].c ;
23     }
24     for(int j=1; j<num; j++)//判断有无负环
25     if(dis[e[j].b]>dis[e[j].a]+e[j].c)
26     return 1 ;//表示有负环
27     return 0 ;
28 }
29 int main()
30 {
31     int t ;
32     cin>>t ;
33     while(t--)
34     {
35        int a, b, c ;
36        num = 1 ;
37        cin>>n>>m>>w ;
38        for(int i=1; i<=m; i++) //由于paths的双向性，两个方向权值相等，注意指针的移动 
39        {
40            cin>>a>>b>>c ;
41            e[num].a = a ;
42            e[num].b = b ;
43            e[num].c = c ;
44            num++ ;
45            e[num].b = a ;
46            e[num].a = b ;
47            e[num].c = c ;
48            num++ ;
49        }
50        for(int i=1; i<=w; i++)//单向边负环
51        {
52            cin>>a>>b>>c ;
53            e[num].a = a ;
54            e[num].b = b ;
55            e[num].c = (-1)*c ;
56            num++ ;
57        }
58        if(bellman_ford())
59        cout<<"YES"<<endl ;
60        else
61        cout<<"NO"<<endl ;
62     }
63     return 0 ;
64 }

对Bellman_ford的小优化 ,加上flag标志 250MS

View Code

 1 #include<iostream>
 2 using namespace std ;
 3 #define INF 1>>28
 4 #define N 6000
 5 struct node
 6 {
 7     int a ;
 8     int b ;
 9     int c ;
10 }e[N] ;
11 int n, m, w, num ;
12 int bellman_ford()
13 {
14     int dis[N] ;
15     for(int i=1; i<=n; i++)
16     dis[i] = INF ;
17     dis[1] = 0 ;//以这个为源点
18     for(int i=1; i<n; i++)//松弛n-1次就必定找出最短路径
19     {
20         bool flag = false ;
21         for(int j=1; j<num; j++)
22         if(dis[e[j].b]>dis[e[j].a]+e[j].c)
23         {
24             dis[e[j].b] = dis[e[j].a] + e[j].c ;
25             flag = true ; //relax对路径有更新 
26         }
27         if(!flag)//只要某一次relax没有更新，说明最短路径已经查找完毕，或者部分点不可达，可以跳出relax  
28         break ;
29     }
30     for(int j=1; j<num; j++)//判断有无负环
31     if(dis[e[j].b]>dis[e[j].a]+e[j].c)
32     return 1 ;//表示有负环
33     return 0 ;
34 }
35 int main()
36 {
37     int t ;
38     cin>>t ;
39     while(t--)
40     {
41        int a, b, c ;
42        num = 1 ;
43        cin>>n>>m>>w ;
44        for(int i=1; i<=m; i++) //由于paths的双向性，两个方向权值相等，注意指针的移动
45        {
46            cin>>a>>b>>c ;
47            e[num].a = a ;
48            e[num].b = b ;
49            e[num].c = c ;
50            num++ ;
51            e[num].b = a ;
52            e[num].a = b ;
53            e[num].c = c ;
54            num++ ;
55        }
56        for(int i=1; i<=w; i++)//单向边负环
57        {
58            cin>>a>>b>>c ;
59            e[num].a = a ;
60            e[num].b = b ;
61            e[num].c = (-1)*c ;
62            num++ ;
63        }
64        if(bellman_ford())
65        cout<<"YES"<<endl ;
66        else
67        cout<<"NO"<<endl ;
68     }
69     return 0 ;
70 }

spfa看是否有一个点进入队列等于n次，375 MS

应该是数据比较少吧spfa竟然最慢

View Code

 1 #include <iostream>
 2 #include<cstring>
 3 #include<queue>
 4 #define INF 0x3f3f3f
 5 using namespace std;
 6 struct node
 7 {
 8     int v,w,next;
 9 }e[6000];
10 int head[501],vis[501],dis[501],c[501];
11 int t ;
12 void init()
13 {
14      t = 0;
15      memset(head,-1,sizeof(head));
16 }
17 void add(int u,int v,int w)
18 {
19      e[t].v = v;
20      e[t].w = w;
21      e[t].next = head[u];
22      head[u] = t;
23      t++;
24 }
25 void spfa(int n)
26 {
27      int i, k, flag = 1;
28      memset(vis,0,sizeof(vis));
29      memset(c,0,sizeof(c));
30      queue<int>q;
31      for(i = 1; i <= n ; i++)
32      dis[i] = INF;
33      dis[1] = 0;
34      q.push(1);
35      vis[1] = 1;
36      c[1] = 1;
37      while(!q.empty())
38      {
39          k = q.front();
40          if(c[k]==n)
41          {
42              flag = 0;
43              break;
44          }
45 
46          q.pop();
47          vis[k] = 0;
48          for(i = head[k];i!=-1 ; i = e[i].next)
49          {
50              if(dis[k]+e[i].w<dis[e[i].v])
51              {
52                  dis[e[i].v]=dis[k]+e[i].w;
53                  if(!vis[e[i].v])
54                  {
55                      vis[e[i].v] = 1;
56                      q.push(e[i].v);
57                      c[e[i].v]++;
58                 }
59              }
60          }
61      }
62      if(!flag)
63      cout<<"YES"<<endl ;
64      else
65      cout<<"NO"<<endl ;
66 }
67  int main()
68  {
69      int i,n,m,a,b,c,w,p;
70      cin>>p ;
71      while(p--)
72      {
73          cin>>n>>m>>w ;
74          init();
75          for(i = 1; i <= m ; i++)
76          {
77              cin>>a>>b>>c ;
78              add(a,b,c);
79              add(b,a,c);
80          }
81          for(i = 1; i <= w ; i++)
82          {
83              cin>>a>>b>>c ;
84              add(a,b,-c);
85         }
86          spfa(n);
87     }
88      return 0;
89 }