首页 > 代码库 > Dwarf Tower

Dwarf Tower

2024-08-20 01:56:15   210人阅读

　　　　　　　　　　　　　　　　dwarf tower
　　　　　　　　　　　　　　　　　　　　　　　　　　　(dwarf.cpp/c/pas)
【问题描述】
Vasya在玩一个叫做"Dwarf Tower"的游戏，这个游戏中有n个不同的物品，它们的编号为1到n。现在Vasya想得到编号为1的物品。
获得一个物品有两种方式：
1. 直接购买该物品，第i件物品花费的钱为ci
2. 用两件其他物品合成所需的物品，一共有m种合成方式。
请帮助Vasya用最少的钱获得编号为1的物品。


【输入格式】
第一行有两个整数n,m(1<=n<=10000,0<=m<=100000)，分别表示有n种物品以及m种合成方式。
接下来一行有n个整数，第i个整数ci表示第i个物品的购买价格，其中0<=ci<=10^9。
接下来m行，每行3个整数ai,xi,yi，表示用物品xi和yi可以合成物品ai，其中(1<=ai,xi,yi<=n; ai<>xi, xi<>yi, yi<>ai)


【输出格式】
一行，一个整数表示获取物品 1 的最少花费。
技术分享

 


【数据规模与约定】
60%的数据，n<=100
100%的数据，n<=10000，m<=100000

技术分享
#include<cstdio>#include<queue>using namespace std;int n,m;struct node{    long long p,next,f;}s[200002];long long a[10001],c=0,be[10001],x,y,z;bool f[10001]={0};queue<int> d;void add(int x,int y,int z){    c++;    s[c].p=y;//合成z所需要的另一个原料     s[c].next=be[x];//指向另一个合成方案     be[x]=c;    //边表，从x开始     s[c].f=z;//记录父亲； }void bfs(int x){//利用spfa的思想进行bfs     long long xx;    for(int i=1;i<=n;i++){//所有节点都要进行bfs         d.push(i);        f[i]=1;    }    while(!d.empty()){        xx=d.front();        f[xx]=0;        d.pop();        for(int i=be[xx];i;i=s[i].next)            if(a[xx]+a[s[i].p]<a[s[i].f]){//当前合成方案能够更新父亲节点，就将父亲入队；                 a[s[i].f]=a[xx]+a[s[i].p];                if(!f[s[i].f]){                    d.push(s[i].f);                    f[s[i].f]=1;                }            }    }}int main(){    freopen("dwarf.in","r",stdin);    freopen("dwarf.out","w",stdout);    scanf("%d%d",&n,&m);    for(int i=1;i<=n;i++) scanf("%I64d",a+i);    for(int i=1;i<=m;i++){        scanf("%d%d%d",&z,&x,&y);        add(x,y,z);        add(y,x,z);//将(x,y)看成一条边，边是双向的     }    bfs(1);    printf("%d\n",a[1]);    fclose(stdin);    fclose(stdout);    return 0;}
View Code

 

Dwarf Tower


联系
我们