洛谷5340 [TJOI2019]大中锋的游乐场

Luogu

BZOJ

分析

分层图最短路板子题。。。

设 $dis[i][j]$ 表示在节点 $i$ ,汉堡与可乐之差为 $j$ 的最短路。

直接跑 $\mathrm{dijkstra}$ 转移就好了。

然而我因为 dis[v] 写成 dis[i] WA 了两发

代码

// =================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// =================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') c=getchar();
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10,M=100000+10,K=15;

int n,m,k,s,t;
int val[N];

struct Edge { int v,w,nxt; } e[M<<1];
int head[N],cnt=0;

inline void addEdge(int u,int v,int w) {
    e[++cnt]=(Edge){v,w,head[u]},head[u]=cnt;
}

struct node { int u,s,d; };
bool operator <(node a,node b) { return a.d>b.d; }

int dis[N][K<<1];

inline void dijkstra() {
    priority_queue<node> Q; Q.push((node){s,val[s],0});
    memset(dis,0x3f,sizeof(dis)); dis[s][val[s]+K]=0;
    while (!Q.empty()) {
        int u=Q.top().u,s=Q.top().s,d=Q.top().d; Q.pop();
        if (d!=dis[u][s+K]) continue;
        for (re int i=head[u];i;i=e[i].nxt) {
            int v=e[i].v,w=e[i].w;
            if (abs(s+val[v])>k) continue;
            if (dis[u][s+K]+w<dis[v][s+val[v]+K]) {
                dis[v][s+val[v]+K]=dis[u][s+K]+w;
                Q.push((node){v,s+val[v],dis[v][s+val[v]+K]});
            }
        }
    }
}

int main() {
    int T=read();
    while (T--) {
        memset(head,0,sizeof(head)),cnt=0;
        n=read(),m=read(),k=read();
        for (re int i=1;i<=n;++i) val[i]=read()*2-3;
        for (re int i=1;i<=m;++i) {
            int u=read(),v=read(),w=read();
            addEdge(u,v,w),addEdge(v,u,w);
        }
        s=read(),t=read();
        dijkstra();
        int ans=0x3f3f3f3f;
        for (re int i=-k;i<=k;++i) ans=min(ans,dis[t][i+K]);
        if (ans==0x3f3f3f3f) puts("-1");
        else printf("%d\n",ans);
    }
    return 0;
}
最后修改:2019 年 09 月 26 日 01 : 34 PM

发表评论