学步园

说实话这个题目不难，但是就是t了n发之后又wa了n发。

唯一的坑点就是inf要开的足够大，开小了各种奇怪问题。

另外存边的时候不能偷懒用vector了，会t额。。

#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
#define LL long long

using namespace std;

const int maxn = 5e4 + 10;
const LL inf = 98765432123456789;

struct Edge{
        int u, w, pre;
        Edge() {}
        Edge(int _u, int _w, int _pre):
                u(_u), w(_w), pre(_pre) {}
}line[maxn * 4];

struct Node{
        int u, dis;
        Node() {}
        Node(int _u, int _dis):
                u(_u), dis(_dis) {}
        bool operator < (const Node &t) const
        {
                return t.dis < dis;
        }
};
int pre[maxn], w[maxn];
bool vis[maxn];
LL dis[maxn];
int n, m, tot;

void add_line(int a, int b, int c)
{
        line[tot] = Edge(b, c, pre[a]);
        pre[a] = tot++;
}

void dijkstra()
{
        for(int i = 1; i <= n; i++)
                dis[i] = inf;
        dis[1] = 0;
        priority_queue<Node> q;
        Node now(1, 0);
        q.push(now);
        while(!q.empty())
        {
                now = q.top();
                q.pop();
                if(vis[now.u])  continue;
                vis[now.u] = true;
                for(int i = pre[now.u]; i != -1; i = line[i].pre)
                {
                        int x = line[i].w;
                        if(dis[now.u]+x<dis[line[i].u])
                        {
                                dis[line[i].u] = dis[now.u] + x;
                                q.push(Node(line[i].u, dis[line[i].u]));
                        }
                }
        }
}

int main()
{
//        freopen("3013.in", "r", stdin);

        int t, a, b, c;
        LL ans;
        bool flag;
        scanf("%d",&t);
        while(t--)
        {
                memset(pre, -1, sizeof(pre));
                memset(vis, false, sizeof(vis));
                tot = 0;
                ans = 0;
                scanf("%d%d",&n,&m);
                for(int i = 1; i <= n; i++)
                        scanf("%d",&w[i]);
                for(int i = 0; i < m; i++)
                {
                        scanf("%d%d%d", &a, &b, &c);
                        add_line(a,b,c);
                        add_line(b,a,c);
                }
                dijkstra();
                flag = true;
                for(int i = 2; i <= n; i++)
                {
                        if(dis[i] >= inf)
                        {
                                flag = false;
                                break;
                        }
                ans += dis[i] * w[i];
            }
            if(flag)
                printf("%I64d\n",ans);
            else
                printf("No Answer\n");
        }
        return 0;
    }