D.Dwarf Tower

Vasya在玩一个叫做”Dwarf Tower”的游戏，这个游戏中有n个不同的物品，

它们的编号为1到n。现在Vasya想得到编号为1的物品。

获得一个物品有两种方式：

直接购买该物品，第i件物品花费的钱为ci

用两件其他物品合成所需的物品，一共有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 的最少花费。

把每一次更新的节点的父亲放入队列中，然后从队列中取一个，在将和他有关的相邻节点相加与他的父亲相比较，如果有更新继续放入队列，直到没有

#include<bits/stdc++.h>

#define sf scanf

#define pf printf

#define si(a) a.size()

#define pii pair<int,int>

#define scf(x) scanf("%d",&x)

#define scff(x,y) scanf("%d%d",&x,&y)

#define rep(i,a,n) for (int i=a;i<n;i++)

#define per(i,a,n) for (int i=a;i>=n;i--)

#define mm(x,b) memset((x),(b),sizeof(x))

#define scfff(x,y,z) scanf("%d%d%d",&x,&y,&z)

#define de(a) cout << #a << " = " << a << endl

#define dd(a) cout << #a << " = " << a << " "

typedef long long ll;

using namespace std;

const double eps=1e-8;

const int N=1e4+2;

int a[N];

int vis[N];

struct node

{

	int pa,fa;

}t;

vector<node> qa[N];

queue<node> q;

queue<int>v;

void solve()

{

	while(!v.empty() )

	{

		int tt=v.front();

		v.pop();

		vis[tt]=0;

		int len=qa[tt].size();

		rep(i,0,len)

		{

			t=qa[tt][i];

			if(a[t.fa]>a[t.pa]+a[tt])

			{

				if(vis[t.fa]==0)

				{

					vis[t.fa]=1;

					v.push(t.fa);

				}

				a[t.fa]=a[t.pa]+a[tt];

			}

		}

	}

}

int main()

{

//	freopen("dwarf.in","r",stdin);

//	freopen("dwarf.out","w",stdout);

	//输入

	mm(vis,0);

	int n,m;scff(n,m);

	rep(i,1,n+1)

	scf(a[i]);

	rep(i,0,m)

	{

		int x,y,z;

		scfff(x,y,z);

		if(a[x]>a[y]+a[z])

		{

			if(vis[x]==0)

			v.push(x),vis[x]=1;

			a[x]=a[y]+a[z];

		}

		t.fa =x;

		t.pa =y;

		qa[z].push_back(t);

		t.pa =z;

		qa[y].push_back(t);

	}

	solve();

	cout<<a[1];

	return 0;

}

巴特西

D.Dwarf Tower

把每一次更新的节点的父亲放入队列中，然后从队列中取一个，在将和他有关的相邻节点相加与他的父亲相比较，如果有更新继续放入队列，直到没有

最新文章

热门文章