```cpp
#include <bits/stdc++.h>
using namespace std;
constexpr int N=5005,M=5e4+5;
constexpr long long INF=0x3f3f3f3f3f3f3f3fll;
int n,m,S,T,ec{1},eh[N];
int prv[N];
long long dis[N],in[N],h[N];
struct{int nxt,to,w,c;}e[M<<1];
void ebba(int u,int v,int w,int c){
e[++ec]={eh[u],v,w,c},eh[u]=ec;
}
void adde(int u,int v,int w,int c){
ebba(u,v,w,c),ebba(v,u,0,-c);
}
void spfa(int s){
static bool inq[N];
queue<int> q;
memset(h+1,0x3f,n*sizeof(long long));
memset(inq+1,0,n*sizeof(bool));
h[s]=0,q.emplace(s),inq[s]=true;
while(!q.empty()){
int u{q.front()}; q.pop();
inq[u]=false;
for(int i{eh[u]};i;i=e[i].nxt){
if(!e[i].w) continue;
int v{e[i].to},c{e[i].c};
if(h[u]+c<h[v]){
h[v]=h[u]+c;
if(!inq[v]) q.emplace(v),inq[v]=true;
}
}
}
}
bool dij(int s){
static bool vst[N];
using Q=pair<long long,int>;
priority_queue<Q,vector<Q>,greater<Q> > q;
memset(dis+1,0x3f,n*sizeof(long long));
memset(vst+1,0,n*sizeof(bool));
q.emplace(dis[s]=0ll,s);
in[s]=INF;
while(!q.empty()){
int u{q.top().second}; q.pop();
if(vst[u]) continue;
vst[u]=true;
for(int i{eh[u]};i;i=e[i].nxt){
if(!e[i].w) continue;
int v{e[i].to};
long long c{(h[u]-h[v])+e[i].c};
if(dis[u]+c<dis[v]){
prv[v]=i,in[v]=min(in[u],1ll*e[i].w);
q.emplace(dis[v]=dis[u]+c,v);
}
}
}
return dis[T]<INF;
}
pair<long long,long long> mcmf(){
long long ws{0ll},cs{0ll};
spfa(S);
while(dij(S)){
for(int i{1};i<=n;++i) h[i]+=dis[i];
for(int i{T};i!=S;i=e[prv[i]^1].to){
e[prv[i]].w-=in[T],
e[prv[i]^1].w+=in[T];
}
ws+=in[T],cs+=in[T]*h[T];
}
return make_pair(ws,cs);
}
signed main(){
scanf("%d%d%d%d",&n,&m,&S,&T);
for(int i{1};i<=m;++i){
int u,v,w,c; scanf("%d%d%d%d",&u,&v,&w,&c);
adde(u,v,w,c);
}
auto t=mcmf();
printf("%lld %lld\n",t.first,t.second);
return 0;
}
```
by rzh123 @ 2023-11-03 20:21:41
@[rzh123](/user/237530) orz 您同学的 spfa 多快？
by Argvchs @ 2023-11-03 20:27:40
@[Argvchs](/user/533270) 比如 <https://www.luogu.com.cn/record/133127814> 比 <https://www.luogu.com.cn/record/133135084> 快
by rzh123 @ 2023-11-03 20:29:13
@[rzh123](/user/237530) 6
by Argvchs @ 2023-11-03 20:30:39
@[Argvchs](/user/533270) ？所以请问我这个是不是假的？
by rzh123 @ 2023-11-03 20:31:23
@[rzh123](/user/237530) n
by Argvchs @ 2023-11-03 20:34:07
@[Argvchs](/user/533270) 谢谢
那是为什么常数大呢？
by rzh123 @ 2023-11-03 20:34:37
@[rzh123](/user/237530) 稠密图前向星不如 vector 快
by Argvchs @ 2023-11-03 20:36:17
谢谢！
by rzh123 @ 2023-11-03 20:36:29