http://poj.org/problem?id=3159

题目大意：

n个小朋友分糖果，你要满足他们的要求（a b x 意思为b不能超过a x个糖果）并且编号1和n的糖果差距要最大。

思路：

嗯，我先揭发一下，1号是分糖果的孩子，班长大人！（公报私仇啊。。。，欺负N号的小朋友~ 好吧，我开玩笑的）

嗯，这题要求最短路径。为啥是最短？你以前都在玩最长呀~

因为这题要求的是最大的。图的三角不等式有：d[v]- d[u]<=w(u,v);  d[v]<=d[u]+w(u,v); 即而松弛的条件为： if(d[v]>d[u]+w(u,v))   d[v]=d[u]+w(u,v); 通过不断的松弛，使得d的值不断变小，直到满足所有条件，也就是说满足条件的时候就是最大的了~

建立图，b - a <=x 然后就是spfa了，不过这题竟然卡队列了。。看discuss人家用stack，然后我也改了，就这样过了。。。。。。

还有这题不能建立超级源点。

设第i个小孩子分到的糖果为s[i]，那么 有s[i]>=0

而上面的是b-a<=x，由于这题求的是最短路径，所以要改为小于号也就是   -s[i]<=0，然后如果添加一个点比如说0那么就是应该从i到0了，那么就无用了。。。。

#include<cstdio>

#include<cstring>

#include<stack>

using namespace std;

const int MAXN=30000+10;

const int MAXM=350000;

const int INF=-999999;

int n,m,head[MAXN],len,dis[MAXN];

bool vis[MAXN];

struct edge

{

	int to,val,next;

}e[MAXM];

void add(int from,int to,int val)

{

	e[len].to=to;

	e[len].val=val;

	e[len].next=head[from];

	head[from]=len++;

}

void spfa()

{

	int s=1;

	stack<int> q;

	q.push(s);

	vis[s]=true;

	dis[s]=0;

	while(!q.empty())

	{

		int cur=q.top();

		q.pop();

		vis[cur]=false;

		for(int i=head[cur];i!=-1;i=e[i].next)

		{

			int id=e[i].to;

			if(dis[id] > dis[cur] + e[i].val)

			{

				dis[id]=dis[cur]+e[i].val;

				if(!vis[id])

				{

					q.push(id);

					vis[id]=true;

				}

			}

		}

	}

}

int main()

{

	while(~scanf("%d%d",&n,&m))

	{

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

		{

			head[i]=-1;

			dis[i]=-INF;

			vis[i]=false;

		}

		len=0;

		for(int i=0;i<m;i++)

		{

			int from,to,val;

			scanf("%d%d%d",&from,&to,&val);

			add(from,to,val);

		}

		spfa();

		printf("%d\n",dis[n]);

	}

	return 0;

}