记录编号	361080	评测结果	AAAAAAAAAA
题目名称	花园的守护之神	最终得分	100
用户昵称	哒哒哒哒哒！	是否通过	通过
代码语言	C++	运行时间	1.515 s
提交时间	2017-01-03 07:07:11	内存使用	61.39 MiB

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
#define ll long long 
ll read(){
	ll x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
	return x*f;
}
const ll maxn=2010;
const ll maxm=500010;
const ll inf=0x3f3f3f3f;
struct edge{
	ll from,to,next,cap;
	edge(){}
	edge(ll a,ll b,ll c){to=a,next=b,cap=c;}
}e[maxm*2],E[maxm*2];
ll tot,head[maxn];
void add(ll u,ll v,ll w){
	//printf("%d %d %d\n",u,v,w );
	e[++tot]=edge(v,head[u],w);head[u]=tot;
	e[++tot]=edge(u,head[v],0);head[v]=tot;
}
void add1(ll u,ll v,ll w){
	E[++tot].from=u;
	E[tot].to=v;
	E[tot].next=head[u];
	E[tot].cap=w;
	head[u]=tot;
}
ll S,T,n,m,dis[maxn];
bool vis[maxn];
/***********************************************/
struct Node{
	ll num,dis;
	Node(){}
	Node(ll a,ll b){num=a,dis=b;}
	bool operator < (const Node &x)const{
		return dis>x.dis;
	}
};
void dijkstra(){
	priority_queue<Node>q;
	memset(dis,0x3f,sizeof dis);
	dis[S]=0;q.push(Node(S,0));
	while(!q.empty()){
		Node node=q.top();q.pop();
		ll s=node.num;if(s==T)return;
		if(dis[s]!=node.dis) continue;
		for(ll i=head[s];i;i=E[i].next){
			ll to=E[i].to;
			if(dis[to]>dis[s]+E[i].cap){
				dis[to]=dis[s]+E[i].cap;
				q.push(Node(to,dis[to]));
			}
		}
	}
}
/***********************************************/
queue<ll>q;
bool bfs(){
	memset(dis,0,sizeof dis);
	memset(vis,0,sizeof vis);
	q.push(S),vis[S]=1;
	while(!q.empty()){
		ll s=q.front();q.pop();
		for(ll i=head[s];i;i=e[i].next){
			ll to=e[i].to;
			if(e[i].cap&&!vis[to]){
				q.push(to),dis[to]=dis[s]+1,vis[to]=1;
			}
		}
	}return vis[T]!=0;
}
ll dfs(ll u,ll flow){
	if(u==T) return flow;
	ll cnt=0;
	for(ll i=head[u];i;i=e[i].next){
		ll to=e[i].to;
		if(e[i].cap&&dis[to]==dis[u]+1){
			ll dd=dfs(to,min(e[i].cap,flow));
			e[i].cap-=dd,e[i^1].cap+=dd;
			flow-=dd,cnt+=dd;
			if(!flow) break;
		}
	}return cnt;
}

ll dinic(){
	ll cnt=0;
	while(bfs()) cnt+=dfs(S,inf);
	return cnt;
}
int main(){
	freopen("greendam2002.in","r",stdin);freopen("greendam2002.out","w",stdout);
	n=read(),m=read(),S=read(),T=read();
	for(ll i=1;i<=m;i++){
		ll a=read(),b=read(),c=read();
		add1(a,b,c);add1(b,a,c);
	}
	dijkstra();
	memset(head,0,sizeof head);tot=1;
	for(ll i=1;i<=m*2;i++){
		ll u=E[i].from,v=E[i].to;
		if(dis[u]+E[i].cap==dis[v]) add(u,v,1);
	}
	printf("%lld\n",dinic());
	fclose(stdin);fclose(stdout);
	return 0;
}