【POJ - 3159】Candies （差分约束，卡SPFA）

题干：

在幼儿园的时候，Flymouse是班上的班长。有时班主任会给班上的孩子们带来一大袋糖果，让他们分发。所有的孩子都非常喜欢糖果，经常比较他们和别人买的糖果的数量。一个孩子A可以有这样的想法，尽管可能是另一个孩子B在某些方面比他好，因此他有理由比他应得更多的糖果，但无论他实际得到多少糖果，他都不应该得到比B少的一定数量的糖果，否则他会感到不满意，去喝头茶。雪儿抱怨飞鼠的偏态分布。 当时史努比和Flymouse共享了类。Flymouse总是把他的糖果和史努比的比较，他想在让每个孩子都满意的同时，尽可能地把糖果的数量差异化。现在他又从班主任那里得到了一袋糖果，他能从中得到最大的区别是什么？

Input

输入包含单个测试用例。测试用例以两个整数n和m开始，分别不超过30000和150000。n是班上的孩子数，孩子数从1到n。snoopy和flymouse总是分别是1和n。然后按照m行，每一行依次包含三个整数a、b和c，这意味着孩子a相信孩子b永远不会比他得到更多的c糖果。

Output

只输出一行所需的最大差异。保证差异是有限的。

Sample Input

2 2
1 2 5
2 1 4

Sample Output

5

Hint

32位有符号整数类型可以执行所有算术运算。

解题报告：

  这题因为保证有解，所以直接Dij就好了，，用spfa会被卡，不过好像用栈就可以500ms飘过，当然加fread就100ms以内水过。不过标解应该还是Dijkstra。。。总之吧，，差分约束不一定就是SPFA，长个心眼就好。

AC代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<stack>
#include<cstring>
#define F first
#define S second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pair<int,int> PII;
const int MAX = 2e5 + 5;
const int INF = 0x3f3f3f3f;
struct Edge {
	int to,ne,w;
} e[MAX];
int tot,head[MAX],dis[MAX],vis[MAX],n,m;
void add(int u,int v,int w) {
	e[++tot].to = v;
	e[tot].ne = head[u];
	e[tot].w = w;
	head[u] = tot;
}
void spfa() {
	for(int i = 1; i<=n; i++) dis[i] = INF,vis[i] = 0;
	stack<int> q;
	q.push(1);dis[1] = 0;vis[1] = 1;
	while(!q.empty()) {
		int cur = q.top();q.pop();
		vis[cur] = 0;
		for(int i = head[cur]; ~i; i = e[i].ne) {
			int v = e[i].to;
			if(dis[v] > dis[cur] + e[i].w) {
				dis[v] = dis[cur] + e[i].w;
				if(vis[v] == 0) {
					vis[v] = 1;q.push(v);
				}
			}			
		}		
	}	
}
int main()
{
	while(~scanf("%d%d",&n,&m)) {
		tot=0;
		for(int i = 1; i<=n; i++) head[i] = -1;
		for(int a,b,c,i = 1; i<=m; i++) {
			scanf("%d%d%d",&a,&b,&c);//b-a<=c
			add(a,b,c);
		}
		spfa();
		printf("%d\n",dis[n]);
		
	}
	return 0 ;
}
//00:34-00:46