P3381 73分tle求调EK+spfa

using namespace std;
#include<bits/stdc++.h>
#define ll long long
ll n,m,s,t;	ll u,v,w,c;const ll N=5e3+7;
ll  flag[N][N];
ll ans=0;
ll kk=0;ll kkk=0;
struct edge{
	ll to,nxt,val,cost;
}ed[N<<2];ll head[N];ll cntt=1;
ll dis[N];
ll pre[N];ll vis[N];
void add_t(ll u,ll v,ll w,ll c){
	ed[++cntt].nxt=head[u];
	ed[cntt].to=v;ed[cntt].val=w;head[u]=cntt;
	ed[cntt].cost=c;
	ed[++cntt].nxt=head[v];
	ed[cntt].to=u;ed[cntt].val=0;
	head[v]=cntt;
	ed[cntt].cost=-c;
}
ll ds[N];
ll bfs(){

	memset(vis,0,sizeof(vis));
	memset(dis,0,sizeof(dis));
	memset(ds,0x3f,sizeof(ds));
	queue<ll> q;
	q.push(s);
	vis[s]=1;
	 ds[s]=0;
	dis[s]=0x3f3f3f3f3f3f3f3f;
	while(!q.empty()){
		ll x=q.front();
		q.pop();
		vis[x]=0;
		for(ll i=head[x];i;i=ed[i].nxt){
			if(ed[i].val==0) continue;
			ll v=ed[i].to;
			if(ds[v]>ds[x]+ed[i].cost){
			ds[v]=ds[x]+ed[i].cost;
			dis[v]=min(dis[x],ed[i].val);
			
			pre[v]=i;
			if(!vis[v]){
				q.push(v);
				vis[v]=1;
			}
			
		}
			
		}
	}
	return dis[t]>0;
	
	
}
void upd(){
	ll x=t;
	while(x!=s){
		int v=pre[x];
		ed[v].val-=dis[t];
		ed[v^1].val+=dis[t];
		x=ed[v^1].to;
		

	}
	kk+=dis[t];
	kkk+=dis[t]*ds[t]; 
	
	
	return;
	
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n>>m>>s>>t;
	for(int i=1;i<=m;i++){
		cin>>u>>v>>w>>c;
		
		if(flag[u][v]==0){
			add_t(u,v,w,c);
			flag[u][v]=cntt;
		}else{
			ed[flag[u][v]-1].val+=w;
		}
	}
	
	while(bfs()!=0){
		upd();
	}
	
	cout<<kk<<' '<<kkk;
	

}