[SDOI2010]魔法猪学院（A*，最短路）

[SDOI2010]魔法猪学院（luogu）

Description

题目描述

iPig在假期来到了传说中的魔法猪学院，开始为期两个月的魔法猪训练。经过了一周理论知识和一周基本魔法的学习之后，iPig对猪世界的世界本原有了很多的了解：众所周知，世界是由元素构成的；元素与元素之间可以互相转换；能量守恒……。

能量守恒……iPig 今天就在进行一个麻烦的测验。iPig 在之前的学习中已经知道了很多种元素，并学会了可以转化这些元素的魔法，每种魔法需要消耗 iPig 一定的能量。作为 PKU 的顶尖学猪，让 iPig 用最少的能量完成从一种元素转换到另一种元素……等等，iPig 的魔法导猪可没这么笨！这一次，他给 iPig 带来了很多 1 号元素的样本，要求 iPig 使用学习过的魔法将它们一个个转化为 N 号元素，为了增加难度，要求每份样本的转换过程都不相同。这个看似困难的任务实际上对 iPig 并没有挑战性，因为，他有坚实的后盾……现在的你呀！

注意，两个元素之间的转化可能有多种魔法，转化是单向的。转化的过程中，可以转化到一个元素（包括开始元素）多次，但是一但转化到目标元素，则一份样本的转化过程结束。iPig 的总能量是有限的，所以最多能够转换的样本数一定是一个有限数。具体请参看样例。

输入格式

第一行三个数 N、M、E 表示iPig知道的元素个数（元素从 1 到 N 编号）、iPig已经学会的魔法个数和iPig的总能量。

后跟 M 行每行三个数 si、ti、ei 表示 iPig 知道一种魔法，消耗 ei 的能量将元素 si 变换到元素 ti 。

输出格式

一行一个数，表示最多可以完成的方式数。输入数据保证至少可以完成一种方式。

Solution

根据题意建一张图，用A星算法算出ans，以x~n的最短路f[x]作为估价函数，并用ans的上界（即e/f[1]）来缩小栈规模，然后有个卡A星的点使用面向数据的编程方法水过；

Code

#include <cstdio>

#include <cstdlib>

#include <vector>

#include <queue>

#include <cstring>

using namespace std;

const int N=;

struct node

{

    int v;

    double w;

};

vector <node> link[N],rel[N];

double e,z,f[N];

int n,m,x,y,ans,in[N];

queue <int> q;

void spfa()

{

    memset(f,0x7f,sizeof(f));

    f[n]=,q.push(n);

    while(!q.empty())

    {

        int u=q.front();

        q.pop();

        int size=rel[u].size();

        in[u]=;

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

        {

            node t=rel[u][i];

            if(f[t.v]>f[u]+t.w)

            {

                f[t.v]=f[u]+t.w;

                if(!in[t.v]) in[t.v]=,q.push(t.v);

            }

        }

    }

}

struct mode

{

    int id;

    double v;

    bool operator <(const mode &o)const

    {

        return v>o.v;

    }

};

priority_queue <mode> Q;

void A(int K)

{

    memset(in,,sizeof(in));

    Q.push((mode){,f[]+});

    while(!Q.empty())

    {

        mode t=Q.top();

        Q.pop();

        if(t.v>e) return ;

        if(t.id==n)

        {

            e-=t.v,ans++;

            continue;

        }

        if(++in[t.id]>K) continue;

        int size=link[t.id].size();

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

        {

            node tem=link[t.id][i];

            if(t.v-f[t.id]+f[tem.v]+tem.w<=e && in[tem.v]<K)

                Q.push((mode){tem.v,t.v-f[t.id]+f[tem.v]+tem.w});

        }

    }

}

int main()

{

    scanf("%d%d%lf",&n,&m,&e);

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

    {

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

        link[x].push_back((node){y,z});

        rel[y].push_back((node){x,z});

    }

    if(e==)

    {

        printf("");

        return ;

    }

    spfa();

    A(e/f[]);

    printf("%d\n",ans);

    return ;

}

巴特西

[SDOI2010]魔法猪学院（A*，最短路）

最新文章

热门文章