POJ3635 Full Tank? 优先队列BFS or 分层图最短路 or DP?

然而我也不知道这是啥啊。。。反正差不多。。。哪位大佬给区分一下QWQ。。

---

好的，我把堆的<写反了。。又调了一个小时。。你能不能稳一点。。。。

记录状态：所在位置u，油量c，花费w

扩展状态：

1.如果c+1<=C，就加1升油，为什么只加1升？因为如果这个状态不优，那它就会乖乖待在堆底下，不会多出现冗余状态；如果优，就在下一次扩展继续加油，所以并不会丢状态

2.向所在连边（u，v）更新，如果可以跑过去，就尝试去更新v的状态。

注意不同油量的状态要分开存，十分像分层图？？？

#include<cstdio>

#include<iostream>

#include<queue>

#include<cstring>

#define R register int

using namespace std;

inline int g() {

    R ret=,fix=; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-:fix;

    do ret=ret*+(ch^); while(isdigit(ch=getchar())); return ret*fix;

}

int n,m,t,cnt;

int fir[],w[],d[][];

bool vis[][];

struct edge{

    int v,nxt,w;

    #define vr(i) e[i].v

    #define nxt(i) e[i].nxt

    #define w(i) e[i].w

}e[];

inline void add(int u,int v,int ww) {vr(++cnt)=v,w(cnt)=ww,nxt(cnt)=fir[u],fir[u]=cnt;}

struct node{int u,c,w; bool operator < (const node& y) const {return w>y.w;}

    node() {} node(int uu,int cc,int ww) {u=uu,c=cc,w=ww;}

};

inline void bfs(int s,int t,int C) {

    memset(d,0x3f,sizeof(d)); memset(vis,,sizeof(vis));

    priority_queue<node>q; d[s][]=; q.push(node(s,,));

    while(q.size()) {

        node tmp=q.top(); q.pop(); R u=tmp.u,c=tmp.c,tw=tmp.w;

        vis[u][c]=true;

        if(u==t) {printf("%d\n",tw); return ;}

        if(c+<=C&&!vis[u][c+]&&d[u][c+]>d[u][c]+w[u]) {d[u][c+]=d[u][c]+w[u]; q.push(node(u,c+,d[u][c+]));}

        for(R i=fir[u];i;i=nxt(i)) { R v=vr(i),ew=w(i);

            if(c>=ew&&!vis[v][c-ew]&&tw<d[v][c-ew]) {

                d[v][c-ew]=tw; q.push(node(v,c-ew,d[v][c-ew]));

            }

        }

    } printf("impossible\n");

}

signed main() {

    n=g(); m=g(); for(R i=;i<n;++i) w[i]=g();

    for(R i=,u,v,w;i<=m;++i) u=g(),v=g(),w=g(),add(u,v,w),add(v,u,w);

    t=g(); while(t--) {R C=g(),s=g(),t=g(); bfs(s,t,C);}

}

---

2019.04.26