SPFA模板

1.BFS版本

 1 const int maxn=105;
 2 const int inf=0x3f3f3f3f;
 3 using namespace std;
 4 int n,m,cnt;
 5 int head[maxn],vis[maxn],d[maxn];
 6 struct edge
 7 {
 8     int next;
 9     int to;
10     int w;
11 }e[maxn];
12 void add(int u,int v,int w)
13 {
14     e[cnt].to=v;
15     e[cnt].w=w;
16     e[cnt].next=head[u];
17     head[u]=cnt++;
18 }
19 void bfs(int s)
20 {
21     memset(vis,0,sizeof vis);
22     memset(d,0x3f,sizeof d);
23     int u,v;
24     queue<int> q;
25     vis[s]=1;
26     d[s]=0;
27     while(!q.empty())
28         q.pop();
29     q.push(s);
30     while(!q.empty())
31     {
32         u=q.front();
33         q.pop();
34         for(int i=head[u];i!=-1;i=e[i].next)
35         {
36             v=e[i].v;
37             if(d[v]>d[u]+e[i].w)
38             {
39                 d[v]=d[u]+e[i].w;
40                 if(!vis[i])
41                 {
42                     vis[i]=1;
43                     q.push(v);
44                 }
45             }
46         }
47     }
48 }
49 void spfa(int s)
50 {
51     memset(vis,0,sizeof vis);
52     memset(d,0x3f,sizeof d);
53     int u,v;
54     queue<int>q;
55     vis[s]=1;
56     d[s]=0;
57     while(!q.empty())
58         q.pop();
59     q.push(s);
60     while(!q.empty())
61     {
62         u=q.front();
63         q.pop();
64         vis[u]=0;
65         for(int i=head[u];i!=-1;i=e[i].next)
66         {
67             v=e[i].v;
68             if(d[v]>d[u]+e[i].w)
69             {
70                 d[v]=d[u]+e[i].w;
71                 if(!vis[v])
72                 {
73                     vis[v]=1;
74                     q.push(v);
75                 }
76             }
77         }
78     }
79 }

2.DFS版本

 1 int head[maxn],d[maxn];
 2 bool flag,vis[maxn];
 3 struct edge
 4 {
 5     int next;
 6     int to;
 7     int w;
 8 }e[maxn];
 9 void add(int u,int v,int w)
10 {
11     e[cnt].to=v;
12     e[cnt].w=w;
13     e[cnt].next=head[u];
14     head[u]=cnt++;
15 }
16 void spfa(int s)
17 {
18     int u,v,w;
19     vis[s]=1;
20     for(int i=head[u];i!=-1;i=e[i].next)
21     {
22         if(d[e[i].v]>d[e[i].u]+e[i].w)
23         {
24             if(vis[e[i].v])
25             {
26                 flag=0;
27                 return;
28             }
29             d[e[i].v]=d[e[i].e]+e[i].w;
30             spfa(e[i].v);
31         }
32     }
33     vis[s]=0;
34 }