　luoguP3393逃离_僵尸岛_

一道洛谷不知道哪门子月赛的题

可以用此题来练习最短路算法

SPFA和dijkstra的练习题（关于Floyed，他死了

思路：

　　本题是最短路板子。

　　

　　首先就是建立虚点0连向被控制的点，令边长为1，SPFA一遍，求出各点到虚点的距离，然后判断没被控制的各点距离是否不大于s+1，就能处理出所有危险的点，标记一下。

　　然后就是跑再一遍SPFA，每次判断连向的点是否被标记，然后选择边权差分约束。

　　但是这样算会算上到了n点的花费，而题意到了n点就不需要花费了，于是最后输出的答案还得减去多加的到n点的花费，然后就OK了（注意答案会爆int）。

code:

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<queue>

#define N 100005

#define M 200005

#define INF 1e18

#define ll long long

using namespace std;

struct edge {

    int to;

    int from;

}e[M<<1];

int cnt,head[N];

inline void add_edge(int x,int y){

    e[++cnt].from = y;

    e[cnt].to = head[x];

    head[x] = cnt;

}

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

ll dis[N];

int vis[N],c[N];

void SPFA() {

    queue <int> q;

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

    memset(dis,0x3f3f3f,sizeof(dis));

    for(int i = 1 ; i <= k ; i++){

        dis[c[i]] = 0;

        vis[c[i]] = 1;

        q.push(c[i]);

    }

    while(!q.empty()) {

        int u = q.front();

        q.pop();

        vis[u] = 0;

        for(int i = head[u] ; i ; i = e[i].to) {

            int v = e[i].from;

            if(dis[v] > dis[u] + 1) {

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

                if(!vis[v]) {

                    vis[v] = 1;

                    q.push(v);

                }

            }

        }

    }

}

ll w[N];

void spfa(){

    queue <int> q;

    for(int i = 1 ; i <= n ; i++) {

        if(dis[i] <= s) w[i] = Q;

        else w[i] = P;

        dis[i] = INF;

    }

    for(int i = 1 ; i <= k ; i++)

        w[c[i]] = INF;

    vis[1] = 1;

    dis[1] = w[n] = w[1] = 0;

    q.push(1);

    while(!q.empty()) {

        int u = q.front();

        q.pop();

        vis[u] = 0;

        for(int i = head[u] ; i ; i = e[i].to) {

            int v = e[i].from;

            if(dis[v] > dis[u] + w[u]){

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

                if(!vis[v]) {

                    vis[v] = 1;

                    q.push(v);

                }

            }

        }

    }

}

int main() {

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

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

    for(int i = 1 ; i <= k ; i++)

        scanf("%d",&c[i]);

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

        int x,y;

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

        add_edge(x,y);

        add_edge(y,x);

    }

    SPFA();

    spfa();

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

    return 0;

}

巴特西

luogu P3393 逃离僵尸岛

luoguP3393逃离_僵尸岛_

可以用此题来练习最短路算法

思路：

code:

最新文章

热门文章