Dwarf Tower
题目连接：
http://codeforces.com/gym/100269/attachments
Description
Little Vasya is playing a new game named “Dwarf Tower”. In this game there are n different items,
which you can put on your dwarf character. Items are numbered from 1 to n. Vasya wants to get the
item with number 1.
There are two ways to obtain an item:
• You can buy an item. The i-th item costs ci money.
• You can craft an item. This game supports only m types of crafting. To craft an item, you give
two particular different items and get another one as a result.
Help Vasya to spend the least amount of money to get the item number 1.
Input
The first line of input contains two integers n and m (1 ≤ n ≤ 10 000; 0 ≤ m ≤ 100 000) — the number
of different items and the number of crafting types.
The second line contains n integers ci — values of the items (0 ≤ ci ≤ 109
).
The following m lines describe crafting types, each line contains three distinct integers ai
, xi
, yi — ai
is
the item that can be crafted from items xi and yi (1 ≤ ai
, xi
, yi ≤ n; ai ̸= xi
; xi ̸= yi
; yi ̸= ai).
Output
The output should contain a single integer — the least amount of money to spend.
Sample Input
5 3
5 0 1 2 5
5 2 3
4 2 3
1 4 5
Sample Output
2
Hint
题意
有n个物品，每个物品的价格是pi，现在你有m种交换方式，就是ai+bi可以换得一个ci
然后问你最便宜得到第一个物品的价钱是多少
题解：
跑最短路，m就相当于建了m条边。
一开始把所有点都压进队列然后跑spfa就好了
至于中途怎么买过来买过去的我不知道，反正暴力出来就是答案咯
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e4+5;
int d[maxn];
struct edge{
int x,y;
edge() {}
edge(int X,int Y):x(X),y(Y){}
};
vector<edge>E[maxn];
int inq[maxn];
int main()
{
freopen("dwarf.in","r",stdin);
freopen("dwarf.out","w",stdout);
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&d[i]);
for(int i=1;i<=m;i++)
{
int x,y,z;scanf("%d%d%d",&x,&y,&z);
E[y].push_back(edge(z,x));
E[z].push_back(edge(y,x));
}
queue<int> Q;
for(int i=1;i<=n;i++)
Q.push(i),inq[i]=1;
while(!Q.empty())
{
int now = Q.front();
Q.pop();
inq[now]=0;
for(int i=0;i<E[now].size();i++)
{
int v = E[now][i].x;
int u = E[now][i].y;
if(d[v]+d[now]<d[u])
{
d[u]=d[now]+d[v];
if(!inq[u])
inq[u]=1,Q.push(u);
}
}
}
cout<<d[1]<<endl;
}