![POJ 3635 - Full Tank? - [最短路变形][手写二叉堆优化Dijkstra][配对堆优化Dijkstra] POJ 3635 - Full Tank? - [最短路变形][手写二叉堆优化Dijkstra][配对堆优化Dijkstra]](https://image.shishitao.com:8440/aHR0cHM6Ly9ia3FzaW1nLmlrYWZhbi5jb20vdXBsb2FkL2NoYXRncHQtcy5wbmc%2FIQ%3D%3D.png?!?w=700)
题目链接:http://poj.org/problem?id=3635
题意题解等均参考:POJ 3635 - Full Tank? - [最短路变形][优先队列优化Dijkstra]。
一些口胡:
说实话,上次写类似的二维状态最短路Gym 101873C - Joyride - [最短路变形][优先队列优化Dijkstra],我没能把手写二叉堆优化Dijkstra的给写出来。
这次费了点功夫,也算是给写出来了,需要注意的点还是有点多的。而且我终于深刻理解为啥不推荐手写二叉堆了,主要是代码量相比优先队列实在是有点大……
而且耗时好像和优先队列优化Dijkstra没啥差别。
AC代码:
#include<cstdio>
#include<algorithm>
#include<queue>
#include<vector>
#include<cstring>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=1e3+;
const int maxm=1e4+;
const int maxc=+; int n,m,q;
int p[maxn]; struct Edge{
int u,v,w;
Edge(int _u=,int _v=,int _w=){u=_u,v=_v,w=_w;}
};
vector<Edge> E;
vector<int> G[maxn];
void init(int l,int r)
{
E.clear();
for(int i=l;i<=r;i++) G[i].clear();
}
void addedge(int u,int v,int w)
{
E.push_back(Edge(u,v,w));
G[u].push_back(E.size()-);
} int d[maxn][maxc],vis[maxn][maxc];
struct Hnode{
int v,r;
Hnode(){}
Hnode(int _v,int _r) {
v=_v, r=_r;
}
};
struct Heap
{
int sz;
Hnode hp[*maxn*maxc];
int pos[maxn][maxc];
void up(int now)
{
while(now>)
{
int par=now>>;
if(d[hp[now].v][hp[now].r]<d[hp[par].v][hp[par].r]) //子节点小于父节点,不满足小顶堆性质
{
swap(hp[par],hp[now]);
swap(pos[hp[par].v][hp[par].r],pos[hp[now].v][hp[now].r]);
now=par;
}
else break;
}
}
void push(Hnode x) //插入权值为x的节点
{
hp[++sz]=x;
pos[x.v][x.r]=sz;
up(sz);
}
Hnode top(){return hp[];}
void down(int now)
{
while((now<<)<=sz)
{
int nxt=now<<;
if(nxt+<=sz && d[hp[nxt+].v][hp[nxt+].r]<d[hp[nxt].v][hp[nxt].r]) nxt++; //取左右子节点中较小的
if(d[hp[nxt].v][hp[nxt].r]<d[hp[now].v][hp[now].r]) //子节点小于父节点,不满足小顶堆性质
{
swap(hp[now],hp[nxt]);
swap(pos[hp[now].v][hp[now].r],pos[hp[nxt].v][hp[nxt].r]);
now=nxt;
}
else break;
}
}
void pop() //移除堆顶
{
hp[]=hp[sz--];
pos[hp[].v][hp[].r]=;
down();
}
inline void clr()
{
sz=;
memset(pos,,sizeof(pos));
}
}H;
int dijkstra(int c,int s,int t)
{
memset(d,0x3f,sizeof(d));
memset(vis,,sizeof(vis)); H.clr();
d[s][]=, H.push((Hnode){s,});
while(H.sz)
{
int u=H.top().v, r=H.top().r; H.pop();
if(u==t) return d[u][r];
if(vis[u][r]) continue;
else vis[u][r]=; if(r<c) {
d[u][r+]=d[u][r]+p[u], H.push((Hnode){u,r+});
}
for(int i=;i<G[u].size();i++)
{
Edge &e=E[G[u][i]]; int v=e.v;
if(r<e.w || vis[v][r-e.w]) continue;
if(d[v][r-e.w]>d[u][r]) {
d[v][r-e.w]=d[u][r];
if(H.pos[v][r-e.w]) H.up(H.pos[v][r-e.w]);
else H.push((Hnode){v,r-e.w});
}
}
}
return INF;
} int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<n;i++) scanf("%d",&p[i]);
init(,n);
for(int i=,u,v,w;i<=m;i++)
{
scanf("%d%d%d",&u,&v,&w);
addedge(u,v,w);
addedge(v,u,w);
}
scanf("%d",&q);
for(int i=,c,s,t;i<=q;i++)
{
scanf("%d%d%d",&c,&s,&t);
int ans=dijkstra(c,s,t);
if(ans<INF) printf("%d\n",ans);
else printf("impossible\n");
}
}
在百练上面可以使用pb_ds库,所以用在OpenJ_Bailian 3761 - Full Tank?上交了一发配对堆优化的Dijkstra。
如果想自己写结构体类型放进配对堆的话,还要再写一个专门用来比较结构体的类型,里面要重定义"()"操作符。
AC代码:
#include<bits/stdc++.h>
#include<ext/pb_ds/priority_queue.hpp>
using namespace std;
using namespace __gnu_pbds;
const int INF=0x3f3f3f3f;
const int maxn=1e3+;
const int maxm=1e4+;
const int maxc=+; int n,m,q;
int p[maxn]; struct Edge{
int u,v,w;
Edge(int _u=,int _v=,int _w=){u=_u,v=_v,w=_w;}
};
vector<Edge> E;
vector<int> G[maxn];
void init(int l,int r)
{
E.clear();
for(int i=l;i<=r;i++) G[i].clear();
}
void addedge(int u,int v,int w)
{
E.push_back(Edge(u,v,w));
G[u].push_back(E.size()-);
} struct Qnode{
int v;
int d,r;
Qnode(){}
Qnode(int _v,int _d,int _r) {
v=_v, d=_d, r=_r;
}
};
struct Cmp{
bool operator()(const Qnode& a,const Qnode& b)const {
return a.d>b.d;
}
};
typedef __gnu_pbds::priority_queue<Qnode,Cmp,pairing_heap_tag> Heap;
int d[maxn][maxc];
int dijkstra(int c,int s,int t)
{
memset(d,0x3f,sizeof(d)); Heap Q;
Heap::point_iterator id[maxn][maxc]; d[s][]=;
id[s][]=Q.push(Qnode(s,d[s][],));
while(!Q.empty())
{
int u=Q.top().v, r=Q.top().r; Q.pop();
if(u==t) return d[u][r];
if(r<c)
{
d[u][r+]=d[u][r]+p[u];
id[u][r+]=Q.push(Qnode(u,d[u][r+],r+));
}
for(int i=;i<G[u].size();i++)
{
Edge &e=E[G[u][i]]; int v=e.v;
if(r<e.w) continue;
if(d[v][r-e.w]>d[u][r])
{
d[v][r-e.w]=d[u][r];
if(id[v][r-e.w]!=) Q.modify(id[v][r-e.w],Qnode(v,d[v][r-e.w],r-e.w));
else id[v][r-e.w]=Q.push(Qnode(v,d[v][r-e.w],r-e.w));
}
}
}
return INF;
} int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<n;i++) scanf("%d",&p[i]);
init(,n);
for(int i=,u,v,w;i<=m;i++)
{
scanf("%d%d%d",&u,&v,&w);
addedge(u,v,w);
addedge(v,u,w);
}
scanf("%d",&q);
for(int i=,c,s,t;i<=q;i++)
{
scanf("%d%d%d",&c,&s,&t);
int ans=dijkstra(c,s,t);
if(ans<INF) printf("%d\n",ans);
else printf("impossible\n");
}
}