描述 Description
看着正在被上古神兽们摧残的花园，花园的守护之神――小 Bug 同学泪流满面。然而，FZOI 不相信眼泪，小 bug 与神兽们的战争将进行到底！
通过 google，小 Bug 得知，神兽们来自遥远的戈壁。为了扭转战局，小 Bug 决定拖延神兽增援的速度。从戈壁到达花园的路径错综复杂，由若干段双向的小路组成。神兽们通过每段小路都需要一段时间。小 Bug 可以通过向其中的一些小路投掷小 xie 来拖延神兽。她可以向任意小路投掷小 Xie，而且可以在同一段小路上投掷多只小 xie。每只小 Xie 可以拖延神兽一个单位的时间。即神兽通过整段路程的总时间，等于没有小 xie 时他们通过同样路径的时间加上路上经过的所有小路上的小 xie 数目总和。
神兽们是很聪明的。他们会在出发前侦查到每一段小路上的小 Xie 数目，然后选择总时间最短的路径。小 Bug 现在很想知道最少需要多少只小 Xie，才能使得神兽从戈壁来到花园的时间变长。作为花园中可爱的花朵，你能帮助她吗?
输入格式 InputFormat
第 1 行包括一个整数 N，表示地图中路点的个数；一个整数 M，表示小路个数；以及整数 S 和 T，分别表示戈壁和花园的路点编号。N 个路点分别被编号为自然数 1~N。
以下 M 行, 每行三个整数 A、B 和 C，表示路点 A 和 B 之间有一条小路相连，且通过它需要的时间为 C。
输入数据保证两路点间最多只有一条小路相连，且戈壁和花园的路点是连通的。
输出格式 OutputFormat
一个整数，表示使 S 到 T 之间最短路增长所需要的最少的小 xie 的数目。
样例输入 SampleInput
6 11 2 5
2 3 1
2 1 4
2 6 2
5 4 11
5 1 16
5 6 18
4 1 5
4 6 7
3 1 3
3 6 1
1 6 2
样例输出 SampleOutput
3
代码 Code
按照最短路建图，求最小割。
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
const int inf=0x7fffffff/27.11;
int i,j,t,n,m,l,r,k,z,y,x;
int S,T,cnt,ans;
struct edge
{
int to,next,val;
}e[4995005],fe[4995005];
int head[1005],dis[1005];
int fhead[1005],fdis[1005],last[1005];;
bool used[1005];
deque <int> q,fq;
inline void read(int &x)
{
x=0;char ch=getchar();
while (ch<'0' || ch>'9') ch=getchar();
while (ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
}
inline void insert(int u,int v,int w)
{
e[++cnt].to=v;e[cnt].next=head[u];e[cnt].val=w;
head[u]=cnt;
}
inline void finsert(int u,int v,int w)
{
fe[++cnt].to=v;fe[cnt].next=fhead[u];fe[cnt].val=w;
fhead[u]=cnt;
}
inline void spfa(int s)
{
int i,j,t,u,v,w;
memset(used,false,sizeof(used));
for (i=1;i<=n;i++) dis[i]=inf;
while (!q.empty()) q.pop_front();
q.push_back(s);dis[s]=0;used[s]=true;
while (!q.empty())
{
u=q.front();q.pop_front();used[u]=false;
for (i=head[u];i;i=e[i].next)
{
v=e[i].to;w=e[i].val+k;
if (dis[v]>dis[u]+w)
{
dis[v]=dis[u]+w;
if (!used[v])
{
used[v]=true;
if (!q.empty() && dis[v]<dis[q.front()]) q.push_front(v);
else q.push_back(v);
}
}
}
}
}
inline void build()
{
int i,j,t,u,v,w;
cnt=1;
for (i=1;i<=n;i++) for (j=head[i];j;j=e[j].next) if (dis[i]+e[j].val==dis[e[j].to])
{
finsert(i,e[j].to,1);
finsert(e[j].to,i,0);
}
}
inline bool bfs(int s)
{
int i,j,t,u,v,w;
while (!fq.empty()) fq.pop_front();
memset(fdis,-1,sizeof(fdis));
fdis[s]=0;fq.push_back(s);
while (!fq.empty())
{
u=fq.front();fq.pop_front();
for (i=fhead[u];i;i=fe[i].next)
{
v=fe[i].to;
if (fe[i].val && fdis[v]==-1)
{
fdis[v]=fdis[u]+1;
fq.push_back(v);
}
}
}
return (fdis[T]!=-1);
}
inline int find(int s,int low)
{
int i,j,t,f;
f=t=0;
if (s==T) return low;
for (i=(last[s])?last[s]:fhead[s];i;i=fe[i].next)
{
last[s]=i;
if (fe[i].val>0 && fdis[s]+1==fdis[fe[i].to] && (t=find(fe[i].to,min(low,fe[i].val))))
{
fe[i].val-=t;
fe[i^1].val+=t;
low-=t;
f+=t;
if (low==0) break;
}
}
return f;
}
inline void dinic()
{
ans=0;
build();
while (bfs(S))
{
memset(last,0,sizeof(last));
ans+=find(S,inf);
}
}
int main()
{
cnt=0;
read(n);read(m);read(S);read(T);
for (i=1;i<=m;i++)
{
read(x);read(y);read(z);
insert(x,y,z);
insert(y,x,z);
}
spfa(S);
dinic();
printf("%d\n",ans);
return 0;
}