传送门：http://acm.hdu.edu.cn/contests/contest_showproblem.php?cid=589&pid=1007
思路：预处理出最短路，跑最小割
lll的代码：
#include<bits/stdc++.h>
#define maxn 2100
#define maxm 180000
#define inf 0x7fffffff
#define min(a,b) ((a)>(b)?(b):(a))
using namespace std;
int pre[maxm],now[maxn],son[maxm],tot,val[maxm],st[maxm],n,m;
void con(int a,int b,int c){
pre[++tot]=now[a];
now[a]=tot;
son[tot]=b;
val[tot]=c;
st[tot]=a;
}
int pre1[maxm],now1[maxn],son1[maxm],tot1,cap[maxm],opp[maxm],line[maxm<<1];
void con1(int a,int b,int c){
pre1[++tot1]=now1[a];
now1[a]=tot1;
son1[tot1]=b;
cap[tot1]=c;
}
void doit(int a,int b,int c){
con1(a,b,c);
con1(b,a,0);
opp[tot-1]=tot;
opp[tot]=tot-1;
}
int ans,dis[maxn],dep[maxn];bool bb[maxn];
void spfa(){
int head=0,tail=1;
memset(dis,63,sizeof(dis));
memset(dep,-1,sizeof(dep));
memset(bb,0,sizeof(bb));
dis[1]=0;line[1]=1;dep[1]=0;
do{
int x=line[++head];bb[x]=0;
for(int p=now[x];p;p=pre[p])if(dis[x]+val[p]<dis[son[p]]){
dep[son[p]]=dep[x]+1;
dis[son[p]]=dis[x]+val[p];
if(!bb[son[p]]){
bb[son[p]]=true;
line[++tail]=son[p];
}
}else if(dis[x]+val[p]==dis[son[p]]&&dep[son[p]]>dep[x]+1)dep[son[p]]=dep[x]+1;
}while(head!=tail);
for(int i=1;i<=tot;i++)if(dis[st[i]]+val[i]==dis[son[i]])doit(st[i],son[i],1);
ans=m-dep[n];
}
bool bfs(){
int head=0,tail=1;
memset(dep,-1,sizeof(dep));
dep[1]=0;line[1]=1;
do{
int x=line[++head];
for(int p=now1[x];p;p=pre1[p])if(cap[p]&&dep[son1[p]]==-1){
dep[son1[p]]=dep[x]+1;
if(son1[p]==n)return true;
line[++tail]=son1[p];
}
}while(head!=tail);
return false;
}
int dfs(int x,int flow){
if(x==n)return flow;
int ans=0,p;
for(p=now1[x];p;p=pre1[p])if(dep[son1[p]]==dep[x]+1&&cap[p]){
int t=dfs(son1[p],min(flow,cap[p]));
flow-=t;
cap[p]-=t;
cap[opp[p]]+=t;
ans+=t;
if(!flow)break;
}
if(!p)dep[x]=-1;
return ans;
}
int mflow(){
int ans=0;
while(bfs())ans+=dfs(1,inf);
return ans;
}
void work(){
tot=tot1=0;
memset(now,0,sizeof(now));
memset(now1,0,sizeof(now1));
for(int i=0;i<m;i++){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
con(a,b,c);
con(b,a,c);
}
spfa();
printf("%d %d
",mflow(),ans);
}
int main(){
while(scanf("%d%d",&n,&m)!=EOF)work();
return 0;
}