Gym-101242B：Branch Assignment（最短路，四边形不等式优化DP）

题意：要完成一个由s个子项目组成的项目，给b(b>=s)个部门分配，从而把b个部门分成s个组。分组完成后，每一组的任

意两个点之间都要传递信息。假设在(i,j)两个点间传送信息，要先把信息加密，然后快递员从i出发到总部，再加

密，在到j点。出于安全原因，每次只能携带一条消息。现在给出了道路网络、各个部门和总部的位置，请输出快

递员要走的最小总距离。

思路：求最短路dis，排序。 由排序不等式，dis相近的分到一组。 那么就是一个分组问题，可以用四边形不等式； 决策单调性DP； 二分+单调栈； 斜率优化。

#include<bits/stdc++.h>

#define s second

#define f first

#define ll long long

#define rep(i,a,b) for(int i=a;i<=b;i++)

using namespace std;

const int inf=1e9;

const int maxn=;

int Laxt[maxn],Next[maxn],To[maxn],Len[maxn],cnt;

int a[maxn],b[maxn],c[maxn],dis[maxn],N,M,S,B,s[][];

ll dp[][],sum[];

pair<int,int>p[maxn]; int vis[maxn];

void read(int &x){

    x=; char c=getchar();

    while(c>''||c<'') c=getchar();

    while(c>=''&&c<='') x=x*+c-'',c=getchar();

}

void add(int u,int v,int l)

{

    Next[++cnt]=Laxt[u]; Laxt[u]=cnt;

    To[cnt]=v; Len[cnt]=l;

}

struct in{

    int dis,u;

    in(){}

    in(int dd,int uu):dis(dd),u(uu){}

    friend bool operator <(in w,in v){

        return w.dis>v.dis;

    }

};

void SPFA()

{

    rep(i,,M) swap(a[i],b[i]);

    cnt=; rep(i,,N) Laxt[i]=,vis[i]=,dis[i]=inf;

    rep(i,,M) add(a[i],b[i],c[i]);

    priority_queue<in>q; q.push(in(,B+)); dis[B+]=;

    while(!q.empty()){

        int u=q.top().u; q.pop(); vis[u]=;

        for(int i=Laxt[u];i;i=Next[i]){

            int v=To[i];if(dis[v]>dis[u]+Len[i]){

                dis[v]=dis[u]+Len[i];

                if(!vis[v]) vis[v]=,q.push(in(dis[v],v));

            }

        }

    }

}

int main()

{

    while(~scanf("%d%d%d%d",&N,&B,&S,&M)){

       rep(i,,M) read(a[i]),read(b[i]),read(c[i]);

       SPFA();

       rep(i,,B) p[i].s=i,p[i].f=dis[i];

       SPFA();

       rep(i,,B) p[i].f+=dis[i];

       sort(p+,p+B+);

       rep(i,,B) sum[i]=sum[i-]+p[i].f;

       memset(s,,sizeof(s));

       memset(dp,0x3f,sizeof(dp));

       dp[][]=;

       rep(k,,S) s[B+][k]=B;

       rep(k,,S){

         for(int i=B;i>=;i--) {

            for(int j=s[i][k-];j<=s[i+][k]&&j<i;j++){

                if(dp[i][k]>dp[j][k-]+1LL*(i-j-)*(sum[i]-sum[j])){

                   dp[i][k]=dp[j][k-]+1LL*(i-j-)*(sum[i]-sum[j]);

                   s[i][k]=j;

                }

            }

          }

       }

       printf("%lld\n",dp[B][S]);

    }

    return ;

}