[HOJ] 70 植樹問題

每段竹竿脆弱度*該竹竿上的物品重量=每個物品的重量*該物品到根所經過竹竿的脆弱度總和
取每物品到根的最短路

#include<cstdio>
#include<queue>
#include<vector>
#include<algorithm>
#define MAX 50005
#define INF 3000000000
using namespace std;
 
struct node{
    int to,val;
};
vector<node> v[MAX];
queue<int> q;
bool inq[MAX];
int w[MAX],fr,to,val,n,m,now;
long long dis[MAX],ans;
 
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&w[i]);
        dis[i]=INF;
    }
    for(int i=0;i<m;i++){
        scanf("%d%d%d",&fr,&to,&val);
        v[fr].push_back(node{to,val});
        v[to].push_back(node{fr,val});
    }
    dis[1]=0;
    q.push(1);
    inq[1]=true;
    while(!q.empty()){
        now=q.front();
        q.pop();
        inq[now]=false;
        for(int i=0;i<v[now].size();i++){
            if(dis[now]+v[now][i].val<dis[v[now][i].to]){
                dis[v[now][i].to]=dis[now]+v[now][i].val;
                if(!inq[v[now][i].to])q.push(v[now][i].to);
                inq[v[now][i].to]=true;
            }
        }
    }
    for(int i=1;i<=n;i++){
        ans+=w[i]*dis[i];
        if(dis[i]==INF){
            puts("No Answer\n");
            return 0;
        }
    }
    printf("%lld\n",ans);
}