十分简单的一道题.

图这么小，跑一边 Floyd 就得到第一问最短路径的答案.

考虑第二问怎么求：

我们可以先将最短路径组成的图从原图中抽离出来，构成新图 $G$.

我们发现，只要 $G$ 的起点与终点联通，那么最短路径就仍然存在.

所以我们想用最小的代价破坏掉 $G$ 点起点与终点的连通性.

这不就是最小割的定义嘛...... 跑一边最大流即可.

Code:

#include 
     
      #define setIO(s) freopen(s".in","r",stdin) #define maxn 200000 #define N 502 #define ll int#define inf 1000000 using namespace std; int n,m; struct Graph{    int u,v,dis,c;     Graph(int u = 0,int v = 0,int dis = 0,int c = 0) : u(u), v(v), dis(dis), c(c){} }G[maxn]; namespace Dinic{    struct Edge    {        int from,to,cap;         Edge(int a = 0,int b = 0,int c = 0):from(a),to(b),cap(c){}     };     vector 
      
        edges;     vector 
       
         G[N];     queue 
        
          Q;     int current[N], d[N], vis[N],s,t;      void add(int u,int v,int c)    {        edges.push_back(Edge(u,v,c));         edges.push_back(Edge(v,u,0));         int kk = edges.size();         G[u].push_back(kk - 2);         G[v].push_back(kk - 1);     }    int BFS()    {        memset(vis,0,sizeof(vis));         vis[s] = 1, d[s] = 0;         Q.push(s);         while(!Q.empty())        {            int u = Q.front(); Q.pop();             for(int sz = G[u].size(),i = 0;i < sz; ++i)            {                Edge e = edges[G[u][i]];                 if(e.cap > 0 && !vis[e.to])                 {                    vis[e.to] = 1, d[e.to] = d[u] + 1;                     Q.push(e.to);                 }            }        }        return vis[t];     }    int dfs(int x,int cur)    {        if(x == t) return cur;         int f=0,flow = 0;         for(int sz = G[x].size(),i = current[x];i < sz; ++i)        {            current[x] = i;              Edge e = edges[G[x][i]];             if(e.cap > 0 && d[e.to] == d[x] + 1)             {                f = dfs(e.to, min(cur,e.cap));                 cur -= f, flow += f;                 edges[G[x][i]].cap -= f, edges[G[x][i] ^ 1].cap += f;             }            if(cur == 0) break;         }        return flow;     }    int maxflow()    {        int ans = 0;        while(BFS())        {            memset(current,0,sizeof(current));             ans += dfs(s,inf);         }        return ans;     }}; namespace Floyd{    ll dis[N][N];      void init()    {        for(int i = 0;i < N; ++i)             for(int j = 0;j < N; ++j) dis[i][j] = inf;         for(int i = 0;i < N; ++i) dis[i][i] = 0;     }    void calc()    {        for(int k = 1;k <= n; ++k)             for(int i = 1;i <= n; ++i)                 for(int j = 1;j <= n; ++j)                      dis[i][j] = min(dis[i][k] + dis[k][j], dis[i][j]);          for(int i = 1;i <= m; ++i)        {            Graph e = G[i];             if(dis[1][e.u] + dis[e.v][n] + e.dis == dis[1][n]) Dinic :: add(e.u,e.v,e.c);             if(dis[1][e.v] + dis[e.u][n] + e.dis == dis[1][n]) Dinic :: add(e.v,e.u,e.c);          }    }}; int main(){    // setIO("input");     Floyd :: init();     scanf("%d%d",&n,&m);     for(int i = 1,a,b,c,d;i <= m; ++i)    {        scanf("%d%d%d%d",&a,&b,&c,&d);         Floyd :: dis[a][b] = Floyd :: dis[b][a] = c;         G[i] = Graph(a,b,c,d);     }    Floyd :: calc();      printf("%d\n",Floyd :: dis[1][n]);     Dinic :: s = 1, Dinic :: t = n;     printf("%d",Dinic :: maxflow());     return 0; }