POJ3159（差分约束转化成最短路）

题目大意是：A孩子不允许B孩子的糖果多出k个来，假设B孩子的糖果数是dis[v],A孩子的糖果数目是dis[u],则题意满足差分约束：dis[v]-dis[u]<=k,(k>=0),移项得dis[v]<=dis[u]+k,其实这道题从此处可以转化为求结点n的单源最短路径，求最大差异即dis[n]最大（源点dis[1]=0）, 由递推关系得1->2->...->n的路径中需要dis[v]取得最大值：因此此处和spfa算法中的松弛条件相符合。

即if(dis[v]>dis[u]+w)dis[v]=dis[u]+w;

值得学习的是使用栈来实现spfa算法。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=30005;
const int maxm=150005;
struct node
{int v,w;int next;
} edge[maxm];
int edgehead[maxm];
int input[maxm][3];
int dis[maxn];
int vis[maxn];
int stacks[maxn];//构造栈
int k,n,m;//每次调用addedge函数前k=1;
void addedge(int u,int v,int w)
{edge[k].v=v;edge[k].w=w;edge[k].next=edgehead[u];edgehead[u]=k++;
}
void init()
{memset(edge,0,sizeof(edge));memset(edgehead,0,sizeof(edgehead));memset(dis,inf,sizeof(dis));memset(vis,0,sizeof(vis));dis[1]=0;k=1;
}
void spfa()
{int top=1;//栈顶指针vis[1]=1;top++;stacks[top]=1;//入队时栈顶指针先+1，出队时后-1while(top){int u=stacks[top];top--;vis[u]=0;for(int i=edgehead[u]; i; i=edge[i].next){int w=edge[i].w;int v=edge[i].v;if(dis[v]>dis[u]+w){dis[v]=dis[u]+w;if(!vis[v]){top++;stacks[top]=v;vis[v]=1;}}}}
}
int main()
{scanf("%d%d",&n,&m);for(int i=0; i<m; i++)scanf("%d%d%d",input[i],input[i]+1,input[i]+2);init();for(int i=0; i<m; i++)addedge(input[i][0],input[i][1],input[i][2]);spfa();printf("%d\n",dis[n]);return 0;
}