POJ 3013 Big Christmas Tree

ﾀﾞｲｸｽﾄﾗやってごにょごにょするだけ

#include <cstdio>
#include <queue>
#include <utility>
#include <climits>
using namespace std;



typedef unsigned long long int ll;
typedef pair<ll,int> P;
struct edge{int to,cost;};
const ll INF = ULLONG_MAX;
ll d[50003];
int v,e;
priority_queue<P, vector<P>,greater<P> > que;
vector<edge> G[50003];
ll weight[50003];



void dij(int s){
    for(int i = 1;i <= v;i++){
	d[i] = INF;
    }
	d[s] = 0;
	que.push(P(0,s));
	while(!que.empty()){
	    P q = que.top(); que.pop();
	    ll cost = q.first;
	    int num = q.second;
	    if(d[num] < cost)continue;
	    for(int i = 0;i < G[num].size();i++){
		edge es = G[num][i];
		if(d[es.to] > cost + es.cost){
		    d[es.to] = cost + es.cost;
		    que.push(P(d[es.to],es.to));
		
		}
	    }
	}
}



int main(){

    int t;
    scanf("%d",&t);

    while(t--){
	for(int i = 1;i <= v;i++){
	    G[i].clear();
	}

	
	scanf("%d%d",&v,&e);
	for(int i = 1;i <= v;i++){
	    scanf("%lld",&weight[i]);
	}

	for(int i = 0;i < e;i++){
	    int a,b,c;
	    scanf("%d%d%d",&a,&b,&c);
	    edge tmp = {b,c};
	    G[a].push_back(tmp);
	    edge tmp2 = {a,c};
	    G[b].push_back(tmp2);
	}

	dij(1);
	ll ans = 0;
	for(int i = 1;i <= v;i++){
	    if(d[i] == INF){
		ans = -1;
		break;
	    }
	    ans += d[i] * weight[i];
	}

	if(ans == -1){
	    printf("No Answer\n");
	}else{
	    printf("%lld\n",ans);
	}
    }
    return 0;
}