学步园

这个还是要多说点东西。这几天写模版的收获还是很多的，但是由于事比较多，然后自己的心态的问题，所以写的也不怎么好，也没有什么注释什么的。非常的遗憾。

现在我要说一说这个比较好的SPFA算法了，这个其实也是比较像优先队列维护的Dijkstra算法的。但是由于dijkstra算法只能用于正权的边，所以也是无法正确算出答案的。

但是SPFA就不同了，因为它并没有每次取出最优的解，而是选择遍历结果，这样就保证了访问的点我还可以继续更新，直到不能更新，但这样就出现一个问题，每次都可以更新，那是不是出现了死循环呢？这就是SPFA还具有的另一个好的功能，判断负环。如果一个点被加入了大于n-1次的话，那么就说明出现了负环，那这个图就没有最最佳答案了。当然，如果是负环没有耽误到其他的可以得到的结果时，也就是单向边，那么，把环内的所有点的距离都赋值成-1，这样就可以判断哪些是可以得到最终答案，而哪些是得不出的。选择的方法可以是这样：当判断出了有一个点已经被加入了N次了，那么肯定出现了负环了，但是先别着急，再让他进行一圈，把所有的点都重新赋值成-1，然后结束循环就行了。好实现的。

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <queue>
#include <string>

/*
SPFA是可以判断负环的：加入某点的次数大于n-1的时候肯定是存在负环的。
所以SPFA是个很不错的万能算法； 
*/

using namespace std;

const int MAXN = 100 + 11;

const int MAXE = MAXN * MAXN;

const int INF = 0x3fffffff;

int inq[MAXN];

int use[MAXN]; 

int N, M;

int idx;

int d[MAXN];

int head[MAXN];

struct Edge
{
	int from;
	int to;
	int val;
	int next;
}e[MAXE];

queue <int> Q;


void addEdge(int from, int to, int val)
{
	e[idx].from = from;
	e[idx].to = to;
	e[idx].val = val;
	e[idx].next = head[from];
	head[from] = idx++;
}

void init()
{
	for (int i = 0; i <= N; i++)
	{
		d[i] = INF;
	}
	memset(head, -1, sizeof(head));
	memset(inq, 0, sizeof(inq));
	memset(use, 0, sizeof(use));
	idx = 0;
	while (!Q.empty())
	{
		Q.pop();
	}
}

int SPFA(int start)
{
	Q.push(start);
	d[start] = 0;
	inq[start] = 1;
	use[start]++;
	while (!Q.empty())
	{
		int v = Q.front();
		Q.pop();
		inq[v] = 0;
		for (int i = head[v]; i != -1; i = e[i].next)
		{
			int from = e[i].from;
			int to = e[i].to;
			int val = e[i].val;
			if (d[v] + val < d[to])
			{
				d[to] = d[v] + val;
				if (!inq[to])
				{
					Q.push(to);
					use[to]++;
					if (use[to] >= N)
					{
						return -1;
					}
					inq[to] = 1;
				}
			}
		}
	}
	return 1;
}

int main()
{
	while (scanf("%d%d", &N, &M) != EOF)
	{
		int a, b, val;
		init();
		for (int i = 0; i < M; i++)
		{
			scanf("%d%d%d", &a, &b, &val);
			addEdge(a, b, val); //这次我建立单向边； 
		}
		int start, end;
		scanf("%d%d", &start, &end);
		int ans = SPFA(start);
		if (ans == -1)
		{
			printf("This graph has a negtive circle!");
		}
		else
		{
			printf("the ans is : %d\n", d[end]);
		}
	}
	system("pause");
	return 0;
}
/*
4 4
1 2 2
2 3 1
3 4 4
4 2 -5
1
3

4 4
1 2 2
2 3 1
3 4 4
4 2 -6
1
3
*/