T3 最短路 line

// <line.cpp> - Thu Oct  6 08:17:54 2016// This file is made by YJinpeng，created by XuYike‘s black technology automatically.// Copyright (C) 2016 ChangJun High School, Inc.// I don‘t know what this program is.#include <iostream>#include <vector>#include <algorithm>#include <cstring>#include <cstdio>#include <cstdlib>#include <cmath>#include <queue>#define MOD 1000000007#define INF 1e9#define IN inline#define RG registerusing namespace std;typedef long long LL;typedef long double LB;const int MAXN=100010;const int MAXM=100010;inline int max(int &x,int &y) {return x>y?x:y;}inline int min(int &x,int &y) {return x<y?x:y;}inline int gi() {    register int w=0,q=0;register char ch=getchar();    while((ch<‘0‘||ch>‘9‘)&&ch!=‘-‘)ch=getchar();    if(ch==‘-‘)q=1,ch=getchar();    while(ch>=‘0‘&&ch<=‘9‘)w=w*10+ch-‘0‘,ch=getchar();    return q?-w:w;}struct Dijskra{    static const int N=50010,M=100010;    int n,m,t;int d[N],fr[N],a[N];int to[M],ne[M],W[M];bool u[N];    struct node{        int s,p;        bool operator<(node a)const{return s>a.s;}    };    priority_queue<node>q;    void link(int u,int v,int w){        to[++t]=v;ne[t]=fr[u];fr[u]=t;W[t]=w;    }    void read(){        n=gi(),m=gi();        for(int i=1;i<=n;i++)a[i]=gi();        while(m--){            int u=gi(),v=gi(),w=gi();            link(u,v,w);        }    }    void Dij(int begin){        for(int i=1;i<=n;i++)d[i]=INF;        q.push((node){d[begin]=0,begin});memset(u,0,sizeof(u));        while(!q.empty()){            while(u[q.top().p]&&!q.empty())q.pop();            if(q.empty())break;            int x=q.top().p;q.pop();u[x]=1;            for(int o=fr[x],y;y=to[o],o;o=ne[o])                if(d[x]+W[o]<d[y]){                    d[y]=d[x]+W[o];                    q.push((node){d[y],y});                }        }        for(int i=1;i<=n;i++)            if(d[i]==INF){printf("No Answer");exit(0);}        LL ans=0;        for(int i=1;i<=n;i++)ans+=1LL*d[i]*a[i];        printf("%lld",ans);    }}e;int main(){    freopen("line.in","r",stdin);    freopen("line.out","w",stdout);    e.read();e.Dij(1);    return 0;}