首先看题看的很懵..
然后这题直接没想用Djstra做 TLE了。看discuss，Dijstra要用堆优化，也可以用SPFA做。
这里在网上找了这两种做法的区别，点多稠密图用Dij，以为它是操作点的，反之则用SPFA。
好久没做题了，前一段时间尽做水题去了。
还有这一道题的数据巨大，各种WA。要用__int64，同时SPFA中要注意环的问题。dis的初始化也要注意全部初始为无穷大。
先给出SPFA的AC代码：
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
#define MAXN 50010
#define MAXM 200010
#define inf 20000000000
struct Node{
int v,next;
__int64 c;
}edge[MAXM];
bool flag;
int que[MAXM];
int head[MAXN];
int tail[MAXN];
__int64 dis[MAXN];
bool vis[MAXN];
int a[MAXN];
int fa[MAXN];
int n,m,e;
void addEdge(int u,int v,int c)
{
edge[e].v=v;
edge[e].c=c;
edge[e].next=head[u];
head[u]=e;
e++;
edge[e].v=u;
edge[e].c=c;
edge[e].next=head[v];
head[v]=e;
e++;
}
void spfa(int s)
{
memset(vis,false,sizeof(vis));
memset(fa,0,sizeof(fa));
for(int i=0;i<MAXN;i++)
dis[i]=inf;
dis[1]=0;
vis[s]=true;
int front,rear;
front=rear=0;
que[rear++]=s;
while(front!=rear)
{
int pre=que[front++];
vis[pre]=true;
int v;
for(int j=head[pre];j!=-1;j=edge[j].next)
{
v=edge[j].v;
if(dis[v]>dis[pre]+edge[j].c)
{
dis[v]=dis[pre]+edge[j].c;
if(!vis[v])
{
vis[v]=true;
que[rear++]=v;
}
}
}
vis[pre]=false;
}
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
e=0;
memset(head,-1,sizeof(head));
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
for(int i=0;i<m;i++)
{
int v,w,e;
scanf("%d%d%d",&v,&w,&e);
addEdge(v,w,e);
}
if(n==0||n==1)
{
printf("0
");
continue;
}
if(m==0)
{
printf("No Answer
");
continue;
}
spfa(1);
__int64 ans=0;
for(int i=1;i<=n;i++)
{
if(dis[i]==inf)
{
printf("No Answer
");
ans=-1;
break;
}
ans+=dis[i]*a[i-1];
}
if(ans!=-1)
printf("%I64d
",ans);
}
return 0;
}