记录编号	159182	评测结果	AAAAAAAAAA
题目名称	[CQOI2015]网络吞吐量	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.178 s
提交时间	2015-04-20 10:42:08	内存使用	8.76 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
typedef long long LL;
const LL INF=1e16;
const int SIZEN=1050;
int n,m;
LL ori_G[SIZEN][SIZEN]={0};
LL dis[SIZEN]={0};
LL lim[SIZEN]={0};
void Dijkstra(int N,LL c[SIZEN][SIZEN],int s,LL f[SIZEN]){
	static bool used[SIZEN]={0};
	memset(used,0,sizeof(used));
	for(int i=1;i<=N;i++) f[i]=INF;
	f[s]=0;int sum=0;
	while(sum<N){
		int mn=-1;
		for(int i=1;i<=N;i++){
			if(used[i]) continue;
			if(mn==-1||f[i]<f[mn]) mn=i;
		}
		if(mn==-1) break;
		sum++;
		used[mn]=true;
		for(int i=1;i<=N;i++){
			if(used[i]) continue;
			if(f[mn]+c[mn][i]<f[i]) f[i]=f[mn]+c[mn][i];
		}
	}
}
class Edge{
public:
	int from,to;
	LL cap,flow;
};
int S,T;
vector<Edge> edges;
vector<int> c[SIZEN];
bool vis[SIZEN]={0};
int depth[SIZEN]={0};
int cur[SIZEN]={0};
void addedge(int from,int to,LL cap){
	edges.push_back((Edge){from,to,cap,0});
	edges.push_back((Edge){to,from,0,0});
	int tot=edges.size()-2;
	c[from].push_back(tot);
	c[to].push_back(tot+1);
}
queue<int> Q;
bool BFS(int S,int T){
	memset(vis,0,sizeof(vis));
	Q.push(S);vis[S]=true;depth[S]=0;
	while(!Q.empty()){
		int x=Q.front();Q.pop();
		for(int i=0;i<c[x].size();i++){
			Edge &e=edges[c[x][i]];
			if(!vis[e.to]&&e.cap>e.flow){
				vis[e.to]=true;
				depth[e.to]=depth[x]+1;
				Q.push(e.to);
			}
		}
	}
	return vis[T];
}
LL DFS(int x,LL a){
	if(x==T||!a) return a;
	LL flow=0;
	for(int &i=cur[x];i<c[x].size();i++){
		Edge &e=edges[c[x][i]];
		if(depth[x]+1==depth[e.to]){
			LL cf=DFS(e.to,min(a,e.cap-e.flow));
			if(cf){
				flow+=cf;
				a-=cf;
				e.flow+=cf;edges[c[x][i]^1].flow-=cf;
			}
			if(!a) break;
		}
	}
	if(!flow) depth[x]=-1;
	return flow;
}
LL Dinic(void){
	LL flow=0;
	while(BFS(S,T)){
		memset(cur,0,sizeof(cur));
		flow+=DFS(S,INF);
	}
	return flow;
}
void makegraph(void){
	S=1+n,T=n;
	for(int i=1;i<=n;i++) addedge(i,i+n,lim[i]);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(dis[i]+ori_G[i][j]==dis[j]){
				addedge(i+n,j,INF);
			}
		}
	}
}
void read(void){
	scanf("%d%d",&n,&m);
	int a,b,d;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++) ori_G[i][j]=INF;
	}
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&a,&b,&d);
		ori_G[a][b]=ori_G[b][a]=min(ori_G[a][b],(LL)d);
	}
	for(int i=1;i<=n;i++) scanf("%lld",&lim[i]);
}
int main(){
	freopen("cqoi15_network.in","r",stdin);
	freopen("cqoi15_network.out","w",stdout);
	read();
	Dijkstra(n,ori_G,1,dis);
	makegraph();
	printf("%lld\n",Dinic());
	return 0;
}