学步园

输入V,E；

接下来V个数字代表每个节点的重量；

接下来E行每行输入a,b,s;代表A-B距离为S，注意为无向图；求最短路。

注意：数据范围，得开long long 。而且SPFA初始化的时候INF得大。一开始我用inf(1<<28)WA到死。最后用了long long 的INF（1<<60)就过了。真是各种蛋疼。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <queue>
#include <set>
#include <vector>
#include <stack>
#include <map>
#include <iomanip>
#define PI acos(-1.0)
#define Max 150005
#define inf 1<<30
#define LL(x) (x<<1)
#define RR(x)(x<<1|1)
using namespace std;

#define INF (__int64)1<<60//初始化得大。。。
long long price[Max];

struct kdq
{
    int v;
    int kk;
    int next;
} edge[Max];

int q[Max*10];

long long dis[Max];
int head[Max];
bool visit[Max];

void spfa(int n)
{
    for(int i=1;i<=n;i++)
    dis[i]=INF;
    //cout<<dis[1]<<endl;
    dis[1]=0;
    visit[1]=1;
    int num=0,cnt=0;
    q[num++]=1;
    while(num!=cnt)
    {
        int temp=q[cnt++];
        visit[temp]=0;
        for(int i=head[temp]; i!=-1; i=edge[i].next)
        {
            int tt=edge[i].v;
            int ttt=edge[i].kk;
            if(dis[temp]+ttt<dis[tt])
            {
                dis[tt]=dis[temp]+ttt;
                if(!visit[tt])
                {
                    q[num++]=tt;
                    visit[tt]=1;
                }
            }
        }
    }
}
void solve(int n)
{
    long long ans=0;
    for(int i=1; i<=n; ++i)
    {
        if(dis[i]==INF)
        {
            printf("No Answer\n");
            return ;
        }
        ans+=dis[i]*price[i];
    }
    printf("%lld\n",ans);
}

int main()
{
    int i,j,k,l,n,m,T;
    int a,b,s;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        memset(head,-1,sizeof(head));
        memset(visit,0,sizeof(visit));
        long long  tt;
        for(i=1; i<=n; i++)
        {
            scanf("%lld",&price[i]);
        }
        int num=0;
        for(i=0; i<m; ++i)//无向图。
        {
            scanf("%d%d%d",&a,&b,&s);
            edge[num].next=head[a];
            head[a]=num;
            edge[num].kk=s;
            edge[num].v=b;
            num++;
            edge[num].next=head[b];
            head[b]=num;
            edge[num].kk=s;
            edge[num].v=a;
            num++;
        }
        spfa(n);
        solve(n);
    }
    return 0;
}

太不仔细了