Luogu P3393 逃离僵尸岛【最短路】By cellur925

题目大意：（其实概括出来也就基本做完了hh）在一张有$n$个点，$m$条边的无向图上，有$k$个点是不能经过的，而与之距离不超过$s$的点，到他们会花费$Q$元，到其他点会花费$p$元，求1到$n$花费的最小价钱。

概括完题意也就非常明了了。我们需要把图上的点分为三类，这部分可以由一个$bfs$求得。

void bfs()

{

    while(!q1.empty())

    {

        int u=q1.front().second;

        int val=q1.front().first;q1.pop();

        for(int i=head[u];i;i=edge[i].next)

        {

            int v=edge[i].to;

            if(val+<=s&&dan[v]==)

                dan[v]=,q1.push(make_pair(val+,v));

        }

    }

}

之后就是裸的最短路了=w=，注意松弛的时候分类讨论&&开longlong&&最后得出答案的时候减去终点的花费（不住了）

Code

#include<cstdio>

#include<algorithm>

#include<queue>

#include<cstring>

#define maxn 100090

using namespace std;

typedef long long ll;

int n,m,k,s,tot,P,Q;

int head[maxn],dan[maxn],vis[maxn];

ll dis[maxn];

struct node{

    int to,next,val;

}edge[maxn*];

queue<pair<int,int> >q1;

void add(int x,int y)

{

    edge[++tot].to=y;

    edge[tot].next=head[x];

    head[x]=tot;

}

void bfs()

{

    while(!q1.empty())

    {

        int u=q1.front().second;

        int val=q1.front().first;q1.pop();

        for(int i=head[u];i;i=edge[i].next)

        {

            int v=edge[i].to;

            if(val+<=s&&dan[v]==)

                dan[v]=,q1.push(make_pair(val+,v));

        }

    }

}

void dijkstra()

{

    priority_queue<pair<ll,int> >q;

    for(int i=;i<=n;i++) dis[i]=1e18;

    dis[]=;q.push(make_pair(,));

    while(!q.empty())

    {

        int u=q.top().second;q.pop();

        if(vis[u]) continue;

        vis[u]=;

        for(int i=head[u];i;i=edge[i].next)

        {

            int v=edge[i].to;

            if(dan[v]==-) continue;

            if(dan[v]==&&dis[v]>dis[u]+P)

            {

                dis[v]=dis[u]+P;

                q.push(make_pair(-dis[v],v));

            }

            if(dan[v]==&&dis[v]>dis[u]+Q)

            {

                dis[v]=dis[u]+Q;

                q.push(make_pair(-dis[v],v));

            }

        }

    }

}

int main()

{

    scanf("%d%d%d%d",&n,&m,&k,&s);

    scanf("%d%d",&P,&Q);

    for(int i=,x;i<=k;i++) scanf("%d",&x),dan[x]=-,q1.push(make_pair(,x));

    for(int i=;i<=m;i++)

    {

        int x=,y=;

        scanf("%d%d",&x,&y);

        add(x,y),add(y,x);

    }

    bfs();

    dijkstra();

    if(dan[n]==) printf("%lld\n",dis[n]-P);

    else printf("%lld\n",dis[n]-Q);

    return ;

}

巴特西

Luogu P3393 逃离僵尸岛【最短路】By cellur925

最新文章

热门文章