POJ3013 Big Christmas Tree

题目：http://poj.org/problem?id=3013

求每个点到1的最短路。不是最小生成树。

总是WA。看讨论里说INF至少2e10，于是真的A了！

算一下，dis最大可能3276800000，于是开成3276800001，果然可A！还快了16ms(?)！

不过出现了： [Warning] this decimal constant is unsigned only in ISO C90 [enabled by default]。是什么意思呢？

总之以后设上界的时候还是略算一下。何况自己常用的0x 7 f f f f f f f也并不是十分大。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const long long INF=3276800001;
int T,n,m,head[50005],xnt,x,y,c[50005],z;
long long ans,dis[50005];
bool in[50005],flag;
struct Edge{
    int next,to,w;
    Edge(int ne=0,int t=0,int o=0):next(ne),to(t),w(o) {}
}edge[100005];
queue<int> q;
void spfa()
{
    while(q.size())q.pop();
    memset(in,0,sizeof in);
    in[1]=1;dis[1]=0;
    q.push(1);
    while(q.size())
    {
        int k=q.front();q.pop();
        in[k]=0;///!
        for(int i=head[k],v;i;i=edge[i].next)
            if(dis[k]+edge[i].w<dis[v=edge[i].to])
            {
                dis[v]=dis[k]+edge[i].w;
                if(!in[v])
                {
                    in[v]=1;////!
                    q.push(v);
                }
            }
    }
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        memset(head,0,sizeof head);
        ans=0;xnt=0;flag=0;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)scanf("%d",&c[i]),dis[i]=INF;
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d%d",&x,&y,&z);
            edge[++xnt]=Edge(head[x],y,z);head[x]=xnt;
            edge[++xnt]=Edge(head[y],x,z);head[y]=xnt;
        }
        spfa();
        for(int i=2;i<=n;i++)
        {
            if(dis[i]==INF)
            {
                flag=1;break;
            }
            ans+=c[i]*dis[i];
        }
        if(flag) printf("No Answer\n");
        else printf("%lld\n",ans);
    }
    return 0;
}