题意：给定一个无向图，删除某些边有一定的代价，要求删掉使得最短路径减小，求最小代价。
首先要spfa求出起点到各个点的最短距离。对于一条权值为w，起点为i，终点为j的边，设dis[k]为起点到k点的距离，若dis[j]=dis[i]+w，则将该边加入另一个图里，边的容量为删除这条边的代价，则从起点到终点的最大流即为答案。
代码：
#include#include #include #include using namespace std;const int inf=0x3fffffff;const int Maxn=1100000;int to[Maxn],nxt[Maxn],first[Maxn],t[Maxn],c[Maxn];int w[Maxn],too[Maxn],nxtt[Maxn],firstt[Maxn];int n,m,ti,co,u,v,tot=1,e[Maxn];int b[Maxn],cur[Maxn],dis[Maxn];inline void add(int u,int v,int ti,int co) { to[tot]=v; nxt[tot]=first[u]; t[tot]=ti; c[tot]=co; first[u]=tot++;}inline void add(int u,int v,int wi) { too[tot]=v; w[tot]=wi; nxtt[tot]=firstt[u]; firstt[u]=tot++;}void spfa() { queue q; memset(dis,0x3f,sizeof(dis)); memset(e,0,sizeof(e)); q.push(1); dis[1]=0; while(!q.empty()) { int now=q.front(); q.pop(); e[now]=0; for(int i=first[now];i;i=nxt[i]) if(dis[to[i]]>dis[now]+t[i]) { dis[to[i]]=dis[now]+t[i]; if(e[to[i]]==0) { q.push(to[i]); e[to[i]]=1; } } }}bool bfs() { queue q; q.push(1); memset(b,0,sizeof(b)); b[1]=1; while(!q.empty()) { int now=q.front(); q.pop(); for(int i=firstt[now];i;i=nxtt[i]) if(w[i]&&b[too[i]]==0) { b[too[i]]=b[now]+1; q.push(too[i]); } } return b[n];}int dfs(int root,int flow) { if(root==n) return flow; for(int &i=cur[root];i;i=nxtt[i]) if(b[too[i]]==b[root]+1&&w[i]) { int temp=dfs(too[i],min(w[i],flow)); if(temp) { w[i]-=temp; w[i^1]+=temp; return temp; } } return 0;}int dinic() { int ans=0,temp; while(bfs()) { memcpy(cur,firstt,sizeof(cur)); while(temp=dfs(1,inf)) ans+=temp; } return ans;}int main() { // freopen("test.in","r",stdin); scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { scanf("%d%d%d%d",&u,&v,&ti,&co); add(u,v,ti,co); add(v,u,ti,co); } spfa(); tot=2; for(int i=1;i<=n;i++) for(int j=first[i];j;j=nxt[j]) if(dis[to[j]]==dis[i]+t[j]) { add(i,to[j],c[j]); add(to[j],i,0); } printf("%d\n%d\n",dis[n],dinic()); return 0;}