我去,500+点裸Floyd居然给过?!BZOJ这评测机不科学的不是一点两点啊!
求完1-i最短路,再求n-i的最短路,两个sssp,上spfa足矣
然后跑个网络流拿dinic练练手……
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn=505,maxm=124755,inf=0x7ffffff;
struct edg1{int t,w,v,n;}e1[maxm*2];
struct edg2{int t,v,n;}e2[maxm*2];
int pf1[maxn],pf2[maxn],te1,te2;
int f[maxn][maxn];
int vis[maxn],lay[maxn];
int m,n;
void ae1(int s,int t,int w,int v)
{
e1[++te1].t=t;
e1[te1].w=w;
e1[te1].v=v;
e1[te1].n=pf1[s];
pf1[s]=te1;
}
void ae2(int s,int t,int v)
{
e2[te2].t=t;
e2[te2].v=v;
e2[te2].n=pf2[s];
pf2[s]=te2++;
}
bool build()
{
memset(vis,0,sizeof(vis));
memset(lay,-1,sizeof(lay));
queue<int>Q;
Q.push(1);lay[1]=0;
while (!Q.empty())
{
int u=Q.front();Q.pop();
for (int c=pf2[u];~c;c=e2[c].n)
if (e2[c].v&&lay[e2[c].t]==-1)
{
lay[e2[c].t]=lay[u]+1;
Q.push(e2[c].t);
}
}
return lay[n]!=-1;
}
int find(int u,int low)
{
if (u==n)
return low;
int ans=0;
for (int c=pf2[u];(~c)&&low;c=e2[c].n)
{
int tans;
if (lay[e2[c].t]==lay[u]+1&&(tans=find(e2[c].t,min(low,e2[c].v))))
{
e2[c].v-=tans;
e2[c^1].v+=tans;
ans+=tans;
low-=tans;
}
}
return ans;
}
int dinic()
{
int ans=0;
while (build())
{
int tans;
while ((tans=find(1,inf)))
ans+=tans;
}
return ans;
}
int main()
{
int a,b,c,d;
scanf("%d%d",&n,&m);
memset(f,0x3f,sizeof(f));
memset(pf2,-1,sizeof(pf2));
for (int i=1;i<=m;i++)
{
scanf("%d%d%d%d",&a,&b,&c,&d);
f[a][b]=f[b][a]=min(f[a][b],c);
ae1(a,b,c,d);
ae1(b,a,c,d);
}
for (a=1;a<=n;a++)
f[a][a]=0;
for (c=1;c<=n;c++)
for (a=1;a<=n;a++)
for (b=1;b<=n;b++)
f[a][b]=min(f[a][b],f[a][c]+f[c][b]);
for (a=1;a<=n;a++)
for (b=pf1[a];b;b=e1[b].n)
if (f[1][a]+e1[b].w+f[e1[b].t][n]==f[1][n])
{
ae2(a,e1[b].t,e1[b].v);
ae2(e1[b].t,a,0);
}
printf("%d\n%d\n",f[1][n],dinic());
return 0;
}