http://poj.org/problem?id=3013
看到这个题还以为很一般的最短路 dijkstra
第一次用矩阵存边 直接不运行 数据太大，换成链表运行了 TLE ...好吧 看别人的解题报告 dijkstra+优先队列 还有用spfa的 spfa比dijkstra快吗 不清楚 明天写个spfa试试
dijkstra代码 顺便学一下大数的定义 输出
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<queue>
using namespace std;
const __int64 inf = 999999999999;
typedef __int64 lint;
int w[50002],head[50002],visit[50002];
lint dis[50002];
int n,e,s_edge;
struct Node
{int p;lint dis;bool operator < (const Node a)const{return a.dis<dis;}
};struct Edge
{int to,w,next;
}edge[100004];void addedge(int u,int v,int w)
{s_edge++;edge[s_edge].to=v;edge[s_edge].w=w;edge[s_edge].next=head[u];head[u]=s_edge;s_edge++;edge[s_edge].to=u;edge[s_edge].w=w;edge[s_edge].next=head[v];head[v]=s_edge;return ;
}void dijkstra()
{priority_queue<Node>qu;Node st,se;int i;memset(visit,0,sizeof(visit));for(i=1;i<=n;i++)dis[i]=inf;dis[1]=0;st.p=1, st.dis=0;qu.push(st);while(!qu.empty()){st=qu.top();qu.pop();if(visit[st.p])continue;visit[st.p]=1;int f;for(f=head[st.p];f;f=edge[f].next){int g=edge[f].to;if(!visit[g]&&dis[g]>dis[st.p]+edge[f].w){dis[g]=dis[st.p]+edge[f].w;se.p=g;se.dis=dis[g];qu.push(se);}}}return ;
}int main()
{int CASE;scanf("%d",&CASE);while(CASE--){int i,u,v,W;scanf("%d%d",&n,&e);for(i=1;i<=n;i++)scanf("%d",&w[i]);s_edge=0;memset(head,0,sizeof(head));while(e--){scanf("%d%d%d",&u,&v,&W);addedge(u,v,W);}dijkstra();bool flag=true;lint SUM=0;for(i=2;i<=n;i++){if(dis[i]==inf){flag=false ;break;}SUM+=dis[i]*w[i];}if(flag)printf("%I64d\n",SUM);elseprintf("No Answer\n");}return 0;
}