3424:Candies（差分约束，Dijkstra）（配对堆优化

题面链接题解令x-yz表示x最大比y大z。若b-ak1,c-bk2,c-ak3，那么c-a最大为多少呢？显然应该等于min(k1+k2,k

题面链接

题解

令x-y<=z表示x最大比y大z。若b-a<=k1, c-b<=k2, c-a<=k3，那么c-a最大为多少呢？显然应该等于min(k1+k2, k3)。可以用下图来表示示(不擅图丑勿怪)

C++堆优化代码

//链式前向星存图+迪杰斯特拉堆优化 #include#include#include#includeusing namespace std;const int MAX=100005;const int MAXN=400009;const int INF=0x3f3f3f3f;int head[MAX],cnt=0;int t,n,a,b,len;int dist[MAX];bool vis[MAX];struct Edge{ //链式前向星 int next,val,to;}Edge[MAXN];inline void add(int u,int v,int w){ Edge[cnt].to=v; Edge[cnt].val=w; Edge[cnt].next=head[u]; head[u]=cnt++;}struct node{ int pos,dist; //点的位置及距离 node(){} node(int p,int d) { pos=p; dist=d; } bool operator <(const node }};void Dij(int start){ priority_queueque; for(int i=1;idist[v]+Edge[i].val) { dist[to]=dist[v]+Edge[i].val; que.push(node(to,dist[to])); } } }}int main(){ while(scanf("%d%d", for(int i=0;i

C++配对堆优化

#include #includeusing namespace std;using namespace __gnu_pbds;typedef pair pii;typedef __gnu_pbds::priority_queue

Heap;const int maxn=1e5+10;const int INF=0x3f3f3f3f;int n,m,s;struct Edge{ int u,v,w; Edge(int _u=0,int _v=0,int _w=0){u=_u,v=_v,w=_w;}};vector E;vector G[maxn];void addedge(int u,int v,int w){ E.push_back(Edge(u,v,w)); G[u].push_back(E.size()-1);}int d[maxn];void dijkstra(){ memset(d,0x3f,sizeof(d)); Heap Q; Heap::point_iterator id[maxn]; d[s]=0; id[s]=Q.push(make_pair(d[s],s)); while(!Q.empty()) { int u=Q.top().second; Q.pop(); for(int i=0;id[u]+e.w) { d[v]=d[u]+e.w; if(id[v]!=0) Q.modify(id[v],make_pair(d[v],v)); else id[v]=Q.push(make_pair(d[v],v)); } } }}int main(){ while(~scanf("%d%d",//起点 //memset(d,0,sizeof d); memset(G,0,sizeof G); for(int i=1;i<=m;i++) { int u,v,w; scanf("%d%d%d", addedge(u,v,w); } dijkstra(); //for(int i=1;i<=n;i++) printf("%d%s",d[i],((i==n)?"\n":" ")); printf("%d\n",d[n]); }}

【本文由： 阜宁网站制作公司 http://www.1234xp.com/funing.html 欢迎留下您的宝贵建议】