题目：http://poj.org/problem?id=3159
题意：幼稚园分糖果，输入a,b,c表示，小孩a最多只能忍受小孩b的糖果比他多c个。求第一个小孩和最后一个小孩最多可以相差多少个糖果。
卡队列，spfa用队列超时，就改成了栈 就A了。。
以下两点题解是看了网上大神的。。。
1、问题转换：题目所求为w[N]-w[1]的最大值，根据题目所给的一系列的约束条件w[i]-w[j]<=c，我们以孩子为结点，以c作为从j到i的有向边的权值，
构造有向图，此时从1到N我们可以得到多个路径，为了使所有的孩子满意，必须保证对于每个从1到N路径的消耗值cost都有w[N]-w[1]<=c，
则都求最大值max(w[N]-w[1])即为min(cost)，也就转换成了最短路径问题。
2、spfa通常是用队列实现的，但本题使用队列会超时，而使用栈实现则可以轻松挺近1000ms大关，这与spfa算法的原理有蛮大关系，
spfa算法的思想就是迭代更新搜索最小值，迭代次序对于算法的运行速度还是有一定影响的，使用栈实现spfa算法，
会优先选择累计松弛次数（就是深搜过程中从根节点到当前节点的节点数）较多的数据进行迭代，
这在很多情况下对于提高运行速度是比较有利的，这道题就是一个很好的例证。
1 #include<iostream> 2 #include<stdio.h> 3 #include<string.h> 4 #include<stack> 5 using namespace std; 6 7 const int INF=1<<28; 8 int cnt,head[150010],d[150010],vis[150010],n,m; 9 stack<int>q; 10 11 struct node 12 { 13 int u,v,w,next; 14 } edge[150010]; 15 16 void spfa(int s) 17 { 18 int i,u,v; 19 for(i=1; i<=n; i++) 20 d[i]=INF; 21 d[s]=0; 22 q.push(s); 23 vis[s]=1; 24 while(!q.empty()) 25 { 26 u=q.top(); 27 q.pop(); 28 vis[u]=0; 29 for(i=head[u]; i!=-1; i=edge[i].next) 30 { 31 v=edge[i].v; 32 if(d[u]+edge[i].w<d[v]) 33 { 34 d[v]=d[u]+edge[i].w; 35 if(!vis[v]) 36 { 37 vis[v]=1; 38 q.push(v); 39 } 40 } 41 } 42 } 43 }; 44 int main() 45 { 46 int u,v,w; 47 while(~scanf("%d%d",&n,&m)) 48 { 49 cnt=0; 50 memset(head,-1,sizeof(head)); 51 memset(vis,0,sizeof(vis)); 52 while(m--) 53 { 54 scanf("%d%d%d",&u,&v,&w); 55 edge[cnt].u=u; 56 edge[cnt].v=v; 57 edge[cnt].w=w; 58 edge[cnt].next=head[u]; 59 head[u]=cnt++; 60 } 61 spfa(1); 62 printf("%d ",d[n]); 63 } 64 }