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;}