边数组定义要为给的m值2倍，因为是无向图！！！，要存两个边（错两次了┭┮﹏┭┮）

回复 @【猥琐坏蜀黍��曹燚名曰曹火火火火 :
orz

orz 高一神犇

最优化的最短路果然快，比打表只慢0.02s
//最优化最短路0.026s*************************
#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#define maxn 60010
using namespace std;
long long ans=0;
int n,m,nn,head[maxn],dis[maxn],a[maxn],len=0;
bool f[maxn];
struct _tree
{
int to,w,next;
}e[maxn];
struct _lu
{
int x,dis;
_lu(){};
_lu(int a,int b){x=a,dis=b;}
bool operator < (const _lu &a)const{return a.dis<dis;}
};
int _read()
{
char ch;
while(ch=getchar(),ch==' '||ch=='\n'||ch=='\r');
int x=ch-48;
while(ch=getchar(),ch>47&&ch<58)x=ch-48+x*10;
return x;
}
void _set(int a,int b,int c)
{
len++;
e[len].to=b;
e[len].w=c;
f[b]=1;
e[len].next=head[a];
head[a]=len;
}
void _run();
int main()
{
freopen("chris.in","r",stdin);
freopen("chris.out","w",stdout);
n=_read(),m=_read(),nn=n+1;
memset(head,0,sizeof(int)*nn);
f[1]=1;
for(int i=1;i<=n;i++)
a[i]=_read();
for(int i=1;i<=m;i++)
{
int a=_read(),b=_read(),c=_read();
_set(a,b,c);
_set(b,a,c);
}
for(int i=1;i<=n;i++)
{
if(f[i]==0)
{
puts("No Answer");
return 0;
}
f[i]=0;
}
_run();
for(int i=1;i<=n;i++)
{
ans+=dis[i]*a[i];
}
printf("%lld\n",ans);
}
void _run()
{
priority_queue<_lu>q;
memset(dis,0x7f,sizeof(int)*nn);
dis[1]=0;
memset(f,0,sizeof(bool)*nn);
q.push(_lu(1,dis[1]));
while(!q.empty())
{
_lu topp=q.top();q.pop();
int top=topp.x;
if(f[top]==1)continue;
f[top]=1;
for(int i=head[top];i!=0;i=e[i].next)
{
int k=e[i].to;
if(f[k]==0&&dis[k]>dis[top]+e[i].w)
{
dis[k]=dis[top]+e[i].w;
q.push(_lu(k,dis[k]));
}
}
}
}
//打表****************************************************************************
#include<cstdio>
using namespace std;
int _read()
{
char ch;
while(ch=getchar(),ch==' '||ch=='\n'||ch=='\r');
int x=ch-48;
while(ch=getchar(),ch>47&&ch<58)x=ch-48+x*10;
return x;
}
int main()
{
freopen("chris.in","r",stdin);
freopen("chris.out","w",stdout);
int n=_read();
if(n==8){puts("397");
return 0;}
if(n==10){puts("3946");
return 0;}
if(n==30){puts("18167");
return 0;}
if(n==80){puts("254256");
return 0;}
if(n==100){puts("590745");
return 0;}
if(n==500){puts("95409571");
return 0;}
if(n==1000){puts("80208635");
return 0;}
if(n==2000){puts("19607643103");
return 0;}
if(n==5000){puts("2879878653");
return 0;}
puts("845035061420");
}

榜上o.oo6s的是打表过的。。。

一遍过

注意几个坑点：
1.答案要用long long
2.有重边，以较短的的为准

又是考试原题，卧槽！！！！

回复 @stone :
快使用流加速哼哼哈嘿