Dwarf Tower（spfa）

原题链接

题意

先给了 $n$ 个数，告诉你制作第 $i$ 件物品物品需要 $a_i$ 元，然后给 $m$ 个关系，每行 $a,b,c$ ，表示第 $a$ 件物品可以用第 $b,c$ 件物品合成，问最后合成第一件物品要多少元？

思路

设一个虚拟点，一开始给的 $n$ 个数就是每个点到虚拟点的距离，然后给的是点之间的关系，比如 $a,b,c$ ，$a=b+c$，可以理解为 c点到 $a$ 点的距离为 $b$ ，$b$ 点到 $a$ 点的距离为 $a$ ，好了，就按这种办法建图，最后要求的是点1的距离，跑 $spfa$ 即可。

注意点

要用文件输入

freopen("dwarf.in", "r", stdin);
freopen("dwarf.out", "w", stdout);

代码

#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N = 2e6 + 10;
int d[N];
int h[N], e[N], ne[N], w[N], idx;
void add(int a, int b, int c)
{
    e[idx] = b;w[idx] = c;ne[idx] = h[a];h[a] = idx ++;
}
bool st[N];
queue<int> q;
void spfa()
{
    while (!q.empty()){
    int t = q.front();q.pop();st[t] = 0;for (int i = h[t]; i != -1; i = ne[i]){
    int j = e[i];if (d[j] > d[t] + d[w[i]]){
    d[j] = d[t]  + d[w[i]];if (!st[j]) {
    q.push(j);st[j] = 1;}}}}
}
signed main()
{
    freopen("dwarf.in", "r", stdin);freopen("dwarf.out", "w", stdout);int n, m;cin >> n >> m;memset(h, -1, sizeof h);for (int i = 1; i <= n; i ++ )	scanf("%d", &d[i]);for (int i = 1; i <= m; i ++ ){
    int a, b, c;scanf("%d%d%d", &a, &b, &c);add(c, a, b);add(b, a, c);}for (int i = 1; i <= n; i ++ ){
    q.push(i);st[i] = 1;}spfa();cout << d[1];return 0;
}

总结

很难把题目转换为学过的知识点，像这题，一开始看的时候根本没有想到用最短路。