POJ3313 【随便写了个spfa就一A了，嗨皮】

我顺便明白了。。。。英文题意理解其实好大一部分还是靠感觉，然后自己猜题意，试题意。

你要是纠结于英文你就跪了。

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <queue>using namespace std;typedef long long LL;const int maxn=50005;const LL INF=6000000000;bool vis[maxn*2];int a[maxn*2],u[maxn*2],v[maxn*2],w[maxn*2],cost[maxn*2],first[maxn*2],next[maxn*2];LL d[maxn];int n,e;queue<int> q;LL spfa(){    LL ans=0;    memset(vis,0,sizeof(vis));    for(int i=1;i<=n;i++) d[i]=(i==1)?0:INF;    q.push(1);    while(!q.empty())    {        int x=q.front();q.pop();        vis[x]=false; //清除在队列中标志。        for(int e=first[x];e!=-1;e=next[e])        if(d[v[e]]>d[x]+w[e])        {            d[v[e]]=d[x]+w[e];            if(!vis[v[e]])            {                vis[v[e]]=true;                q.push(v[e]);            }        }    }    for(int i=1;i<=n;i++)    {        if(d[i]==INF) return 0;        else ans+=a[i]*d[i];    }    return ans;}int main(){    int case_num;    scanf("%d",&case_num);    while(case_num--)    {        scanf("%d%d",&n,&e);        for(int i=1;i<=n;i++)            scanf("%d",&a[i]);        memset(first,-1,sizeof(first));        for(int i=1;i<=2*e;i+=2)        {            scanf("%d%d%d",&u[i],&v[i],&w[i]);             next[i]=first[u[i]];//还只能先处理next,后first             first[u[i]]=i;            u[i+1]=v[i];//双向边            v[i+1]=u[i];            next[i+1]=first[u[i+1]];            first[u[i+1]]=i+1;            w[i+1]=w[i];        }        if(v==0) {printf("0\n");continue;}        if(e==0) {printf("0\n");continue;}        LL ans=spfa();        if(ans==0)            printf("No Answer\n");        else            printf("%lld\n",ans);    }    return 0;}