题解：P7082 [NWRRC2013] Dwarf Tower

· · 题解

这一题很水

这一题还是有一些难度的。

首先理解题目：

发现一件衣服的获取方式有：豪横的直接用 c_i 元直接买下第 i 件衣服，也可以用第 x_i 件衣服和第 y_i 件衣服制作第 a_i 件衣服。

由此推出一件衣服最少价格公式为：

min(q[a[j]],q[b[j]]+q[c[j]])

那么我们用一个数组把这 n 件衣服的最小价格存起来再输出第 1 件衣服就可以了。这样的时间复杂度就是 O(m)。

代码：

#include<bits/stdc++.h>
using namespace std;
int q[100005],n,m;
int a[100005],b[100005],c[100005];
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>q[i];
    for(int i=1;i<=m;i++) cin>>a[i]>>b[i]>>c[i];
    for(int j=1;j<=m;j++)
        q[a[j]]=min(q[a[j]],q[b[j]]+q[c[j]]);
    cout<<q[1];
    return 0;
}

可是这样做有可能存在制作一件衣服的材料衣服有更便宜的制作方式在后面，导致价格不是最少而出错。

所以我们再套一层循环，重复计算一件衣服最少价格，这样答案就正确了，时间复杂度就是 O(n \cdot m)。

参考代码如下：

#include<bits/stdc++.h>
using namespace std;
int q[100005],n,m;
int a[100005],b[100005],c[100005];
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>q[i];
    for(int i=1;i<=m;i++) cin>>a[i]>>b[i]>>c[i];
    for(int i=1;i<=n;i++)//为避免出错而套的循环 
        for(int j=1;j<=m;j++)
            q[a[j]]=min(q[a[j]],q[b[j]]+q[c[j]]);//衣服的最少价格公式 
    cout<<q[1];
    return 0;
}