首页 > 代码库 > poj 3159 candies (差分约束 spfa+stack)
poj 3159 candies (差分约束 spfa+stack)
http://poj.org/problem?id=3159
题意：一个班有n个人 每人分到若干糖果 且u的糖果数不能比v少w个 求第1个人与第n个人最大数量差
照着模板spfa+queue果断tle了
之后照着题解说的把queue改成stack就过了 但是还不明白为什么会快
而且如果用数组直接模拟会比stl更快
#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#include<cmath>#include<queue>#include<stack>#define INF 10000000using namespace std;int n,m;int d[30000+10];struct Node{ int u,v,w;};Node node[150000+20];int first[30000+20];int next [150000+20];int main(){ int i,j,k; int u,v,w; while(scanf("%d%d",&n,&m)!=EOF) { //memset(mat,0,sizeof(mat)); for(i=2;i<=n;i++) d[i]=INF; d[1]=0; for(int i=1;i<=n;i++) first[i]=-1; for(i=1;i<=m;i++) { scanf("%d%d%d",&u,&v,&w); //u+w>=v node[i].u=u; node[i].v=v; node[i].w=w; next[i]=first[u]; first[u]=i; } int q[30000+10]; int tot=0; bool inq[30000+10]; memset(inq,0,sizeof(inq)); q[tot++]=1; while(tot) { int x=q[--tot]; inq[x]=false; for(int e=first[x];e!=-1;e=next[e]) { if(d[node[e].v]>d[x]+node[e].w) { d[node[e].v]=d[x]+node[e].w; if(!inq[node[e].v]) { inq[node[e].v]=true; //q.push(node[e].v); q[tot++]=node[e].v; } } } } printf("%d\n",d[n]); } return 0;}
#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#include<cmath>#include<queue>#include<stack>#define INF 10000000using namespace std;int n,m;int d[30000+10];struct Node{ int u,v,w;};Node node[150000+20];int first[30000+20];int next [150000+20];int main(){ int i,j,k; int u,v,w; while(scanf("%d%d",&n,&m)!=EOF) { //memset(mat,0,sizeof(mat)); for(i=2;i<=n;i++) d[i]=INF; d[1]=0; for(int i=1;i<=n;i++) first[i]=-1; for(i=1;i<=m;i++) { scanf("%d%d%d",&u,&v,&w); //u+w>=v node[i].u=u; node[i].v=v; node[i].w=w; next[i]=first[u]; first[u]=i; } stack<int> q; bool inq[30000+10]; memset(inq,0,sizeof(inq)); q.push(1); while(!q.empty()) { int x=q.top(); q.pop(); inq[x]=false; for(int e=first[x];e!=-1;e=next[e]) { if(d[node[e].v]>d[x]+node[e].w) { d[node[e].v]=d[x]+node[e].w; if(!inq[node[e].v]) { inq[node[e].v]=true; q.push(node[e].v); } } } } printf("%d\n",d[n]); } return 0;}
poj 3159 candies (差分约束 spfa+stack)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。