Link:
Solution:
好不容易自己写出来一道水题，练链式前向星的模板调了一小时o(╯□╰)o
思路非常好想，既然要想让最短路不成立，使最短路部分不连通即可
又要求最小代价，就是比较明显的最小割模型了
Tips:
1、关于如何快速将所有最短路部分重新建图
既然$n<=500$，直接上$floyd$，只要判断边的两端到1与$n$的最短距离加上边权的和是否为最短路距离即可
但一旦$n$增大后能如何简便处理呢？我想到的可以建反图从后往前跑一遍，检查每一条边是否属于任意一条最短路
但对于此题可以简便处理：正向判断$dist[x]+l(x,y)$是否为$dist[y]$即可
我们没有必要只筛选出最短路的边，只要保证非最短路到不了终点即可，算是用时间换代码长度吧2333
2、对于链式前向星实现的网络流算法
（1）$edge$数组的下标一定要从0开始，这样才能使得$edge[i]$与$edge[i^1]$互为反边
（2）由于上一条原则，$head$数组一定要初始化为-1，而不是-1与0皆可
以前只用$vector$写还是不太行啊……
Code:
#include <bits/stdc++.h> using namespace std;
const int MAXN=,MAXM=MAXN*MAXN,INF=<<;
int n,m,f[MAXN][MAXN];
struct data{int x,y,t,c;}dat[MAXM]; namespace Max_Flow //最大流
{
int head[MAXN],S,T,level[MAXN],iter[MAXN],tot=-; //数组坐标一定要从0开始
struct edge{int nxt,to,cap;}e[MAXM<<]; void add_edge(int from,int to,int cap)
{
e[++tot].nxt=head[from];e[tot].to=to;e[tot].cap=cap;head[from]=tot;
e[++tot].nxt=head[to];e[tot].to=from;e[tot].cap=;head[to]=tot;
} bool bfs()
{
memset(level,-,sizeof(level));
queue<int> q;q.push(S);level[S]=;
while(!q.empty())
{
int u=q.front();q.pop();
for(int i=head[u];i!=-;i=e[i].nxt)
if(e[i].cap && level[e[i].to]==-)
level[e[i].to]=level[u]+,q.push(e[i].to);
}
return (level[T]!=-);
} int dfs(int v,int f)
{
if(v==T) return f;
int ret=;
for(int &i=iter[v];i!=-;i=e[i].nxt)
{
if(level[e[i].to]==level[v]+ && e[i].cap)
{
int d=dfs(e[i].to,min(f,e[i].cap));
e[i].cap-=d;e[i^].cap+=d;
f-=d;ret+=d;if(!f) break;
}
}
return ret;
} int Dinic()
{
int ret=;
while(bfs())
{
for(int i=;i<MAXN;i++) iter[i]=head[i];
ret+=dfs(S,INF);
}
return ret;
}
} int main()
{
using namespace Max_Flow;
scanf("%d%d",&n,&m);
memset(f,0x3f,sizeof(f));S=;T=n;
for(int i=;i<=n;i++) f[i][i]=;
for(int i=;i<=m;i++)
{
scanf("%d%d%d%d",&dat[i].x,&dat[i].y,&dat[i].t,&dat[i].c);
int x=dat[i].x,y=dat[i].y;
f[x][y]=f[y][x]=dat[i].t;
}
for(int k=;k<=n;k++) //最短路部分
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
printf("%d\n",f[][n]); memset(head,-,sizeof(head)); //head一定要赋为-1
for(int i=;i<=m;i++)
{
int x=dat[i].x,y=dat[i].y;
if(f[][x]+dat[i].t+f[y][n]==f[][n])
add_edge(x,y,dat[i].c);
if(f[][y]+dat[i].t+f[x][n]==f[][n])
add_edge(y,x,dat[i].c);
}
printf("%d\n",Dinic());
return ;
}