Candies POJ - 3159（差分约束模板题，优先队列优化Dijkstra模板）

题意：给n个人派糖果，给出m组数据，每组数据包含A，B，c 三个数， 意思是A的糖果数比B少的个数不多于c,即B的糖果数 - A的糖果数<= c 。 最后求n 比 1 最多多多少糖果

AC代码：

#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=150000+5;
const int inf=0x3f3f3f3f;
int n,m,dis[maxn],vis[maxn];
struct nnode {
	int v,w,next;
} e[maxn*3];
struct node{
	int d,u;
	bool operator<(const node&x)const{
	return d>x.d;
	}
};
int head[maxn*3],cnt;
void add(int u,int v,int w) {
	e[cnt].v=v;
	e[cnt].w=w;
	e[cnt].next=head[u];
	head[u]=cnt++;
}
void dijkstra() {
	fill(dis,dis+n+1,inf);
	memset(vis,0,sizeof(vis));
	priority_queue<node>q;
	q.push(node{dis[1],1});
	dis[1]=0;
	while(!q.empty()) {
		int u=q.top().u;
		q.pop();
		if(vis[u])continue;
		vis[u]=1;
		for(int i=head[u]; i!=-1; i=e[i].next) {
			if(dis[e[i].v]>dis[u]+e[i].w) {
				dis[e[i].v]=dis[u]+e[i].w;
				q.push(node{dis[e[i].v],e[i].v});
			}
		}
	}
	cout<<dis[n]<<endl;

}
int main() {
	scanf("%d%d",&n,&m);
	cnt=1;
	memset(head,-1,sizeof(head));
	for(int i=1; i<=m; i++) {
		int x,y,w;
		scanf("%d%d%d",&x,&y,&w);
		add(x,y,w);
	}
	dijkstra();
}