路由是指通过计算机网络把信息从源地址传输到目的地址的活动，也是计算机网络设计中的重点和难点。网络中实现路由转发的硬件设备称为路由器。为了使数据包最快的到达目的地，路由器需要选择最优的路径转发数据包。例如在常用的路由算法OSPF(开放式最短路径优先)中，路由器会使用经典的Dijkstra算法计算最短路径，然后尽量沿最短路径转发数据包。现在，若已知一个计算机网络中各路由器间的连接情况，以及各个路由器的最大吞吐量（即每秒能转发的数据包数量），假设所有数据包一定沿最短路径转发，试计算从路由器1到路由器n的网络的最大吞吐量。计算中忽略转发及传输的时间开销，不考虑链路的带宽限制，即认为数据包可以瞬间通过网络。路由器1到路由器n作为起点和终点，自身的吞吐量不用考虑，网络上也不存在将1和n直接相连的链路。
Input
输入文件第一行包含两个空格分开的正整数n和m，分别表示路由器数量和链路的数量。网络中的路由器使用1到n编号。接下来m行，每行包含三个空格分开的正整数a、b和d，表示从路由器a到路由器b存在一条距离为d的双向链路。 接下来n行，每行包含一个正整数c，分别给出每一个路由器的吞吐量。
Output
输出一个整数，为题目所求吞吐量。
题解：
先按距离建图，用spfa跑一遍最短路径。
建一个新图，每个点拆成两个点连边，容量为最大吞吐量，如果两个点之间的边在最短路径上，每个点的终点与另一个点的起点连边，跑Dinic算法求最大流。
#include<bits/stdc++.h> using namespace std; typedef long long ll; ll inf=1e18; const int maxn=1e6; int N,M; int head[maxn]; int tol; struct node { int u; int v; ll w; int next; }edge[maxn]; void addedge (int u,int v,ll w) { edge[tol].u=u; edge[tol].v=v; edge[tol].w=w; edge[tol].next=head[u]; head[u]=tol++; } ll d[maxn]; int visit[maxn]; void spfa (int s) { for (int i=1;i<=N;i++) d[i]=inf; d[s]=0; queue<int> q; q.push(s); visit[s]=1; while (!q.empty()) { int u=q.front(); q.pop(); visit[u]=0; for (int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].v; if (edge[i].w>0&&d[v]>d[u]+edge[i].w) { d[v]=d[u]+edge[i].w; if (!visit[v]) { q.push(v); visit[v]=1; } } } } } ll dep[maxn]; ll inque[maxn]; ll vi; ll cur[maxn]; ll maxflow=0; int s,t; bool bfs () { for (int i=1;i<=2*N;i++) cur[i]=head[i],dep[i]=inf,inque[i]=0; dep[s]=0; queue<int> q; q.push(s); while (!q.empty()) { int u=q.front(); q.pop(); inque[u]=0; for (int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].v; if (dep[v]>dep[u]+1&&edge[i].w) { dep[v]=dep[u]+1; if (inque[v]==0) { q.push(v); inque[v]=1; } } } } if (dep[t]!=inf) return 1; return 0; } ll dfs (int u,ll flow) { ll increase=0; if (u==t) { vi=1; maxflow+=flow; return flow; } ll used=0; for (int i=cur[u];i!=-1;i=edge[i].next) { cur[u]=i; int v=edge[i].v; if (edge[i].w&&dep[v]==dep[u]+1) { if (increase=dfs(v,min(flow-used,edge[i].w))) { used+=increase; edge[i].w-=increase; edge[i^1].w+=increase; if (used==flow) break; } } } return used; } ll Dinic () { while (bfs()) { vi=1; while (vi==1) { vi=0; dfs(s,inf); } } return maxflow; } int u[maxn]; int v[maxn]; ll w[maxn]; int main () { memset(head,-1,sizeof(head)); scanf("%d%d",&N,&M); for (int i=0;i<M;i++) { scanf("%d%d%lld",&u[i],&v[i],&w[i]); addedge(u[i],v[i],w[i]); addedge(v[i],u[i],w[i]); } spfa(1); memset(head,-1,sizeof(head)); tol=0; for (int i=0;i<M;i++) { if (d[u[i]]+w[i]==d[v[i]]) { addedge(u[i]+N,v[i],inf); addedge(v[i],u[i]+N,0); } if (d[v[i]]+w[i]==d[u[i]]) { addedge(v[i]+N,u[i],inf); addedge(u[i],v[i]+N,0); } } for (int i=1;i<=N;i++) { int c; scanf("%d",&c); if (i!=1&&i!=N) addedge(i,i+N,c); else addedge(i,i+N,inf); addedge(i+N,i,0); } s=1; t=2*N; printf("%lld ",Dinic()); }