POJ - 3159 Candies 单源最短路模板题

本文主要是介绍POJ - 3159 Candies 单源最短路模板题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接

POJ-3159

题意

分糖，n个小朋友，m个关系，AB间关系的意思是A的糖果最多比B少w个，w为关系的权。求1号和n号最多能差多少糖果。

解法

裸的单源最短路，数据量大跑不了floyd，dij和spfa都是随便跑。

代码

#include<iostream>
#include<cstring>
#include<queue>  
#include<cstdio>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl "\n"
using namespace std;typedef long long ll;typedef pair <int,int> P;const int maxn=35005;const int maxe=155005;const int inf=0x3f3f3f3f;int head[maxn];struct Edge{int to;int next;int w;} edge[maxe];int cnt;int dis[maxn];//存放距离 template <typename T>void read(T &x){x=0;char ch=getchar();ll f=1;while(!isdigit(ch)){if(ch=='-')f*=-1;ch=getchar();}while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}x*=f;}	void init(){cnt=0;memset(head,-1,sizeof(head));return ;}inline void add(int u,int v,int w){edge[cnt].next=head[u];edge[cnt].to=v;edge[cnt].w=w;head[u]=cnt;cnt++;}void dij(int start){memset(dis,0x3f,sizeof(dis));//小顶堆，注意括号间空格，不然会被当成>> priority_queue<P,vector<P>,greater<P> > q;dis[start]=0;q.push(P(0,start));while(!q.empty()){P p=q.top(); q.pop();int v=p.second;//这一行是优化，因为同一个顶点可能多次入队，只需要对该顶点dis最小的进行松弛if(dis[v]<p.first)		continue;for(int i=head[v];i!=-1;i=edge[i].next){int tmp=edge[i].to;if(dis[tmp]>dis[v]+edge[i].w){dis[tmp]=dis[v]+edge[i].w;q.push(P(dis[tmp],tmp));}}}return ;}int main(){int n,m;read(n),read(m);init();while(m--){int u,v,w;read(u),read(v),read(w);add(u,v,w);} dij(1);cout<<dis[n]<<endl;return 0;}