(最短路+最小路径覆盖)

题意：

给一张n个点m条边的有向带权图，给出C个关键点，问沿着最短路径走，从0最少需要出发多少次才能能覆盖这些关键点

\(1 <= n <= 1000\)

\(1 <= m <= 10^5\)

\(1 <= w <= 10^9\)

\(1 <= C <= 300\)

题解：

对所有的关键点建一个新图，对于任意两个关键点

若满足在原图中的最短路\(dis(0,u)+dis(u,v)=dis(0,v)\),

则\(u\)到\(v\)连一条有向边

显然新图一定是个\(DAG\),答案就等于新图的最小不相交路径覆盖

复习一下\(DAG\)上的最小不相交路径覆盖

对于一条路径，起点的入度为0，终点的出度为0，中间节点的出入度都为1每一个点最多只能有1个后继，同时每一个点最多只能有1个前驱。假如我们选择了一条边(u,v)，也就等价于把前驱u和后继v匹配上了。这样前驱u和后继v就不能和其他节点匹配。利用这个我们可以这样来构图：将每一个点拆分成2个，分别表示它作为前驱节点和后继节点。将所有的前驱节点作为A部，所有后继节点作为B部，若原图中存在一条边(u,v)，则连接A部的u和B部的v然后跑二分图匹配,答案就是点数-最大匹配数,也可以这样理解，我们要让结尾结点尽可能少，所以就要尽可能多的配对一个点既可能做为前驱也可能做为后继，所以需要拆点若求DAG上的可相交路径覆盖，求出图的floyd，转化为求不相交路径覆盖即可

#include
    
     #define LL long long#define P pair
     
      using namespace std;const LL inf = 1e15;const int N = 1e3 + 10;vector
      
 G[N];vector
       
         GG[N];LL dis[N][N];int n,m,C;int a[N];void dij(LL dis[],int s){    for(int i = 0;i < n;i++) dis[i] = inf;    dis[s] = 0;    priority_queue
        
       
      
,greater
      
 >q;    q.push(P(0,s));    while(!q.empty()){        P cur = q.top();q.pop();        int u = cur.second;        if(dis[u] < cur.first) continue;        for(auto now:G[u]){            int v = now.second;            if(now.first + dis[u] < dis[v]){                dis[v] = dis[u] + now.first;                q.push(P(dis[v],v));            }        }    }}int match[1000];int vis[1000];bool dfs(int u){    vis[u] = 1;    for(auto v:GG[u]){        int w = match[v];        if(w < 0 || !vis[w] && dfs(w)){            match[v] = u;            return true;        }    }    return false;}int Maxmatch(){    int ans = 0;    memset(match, -1, sizeof(match));    for(int i = 1;i <= C;i++){       memset(vis,0,sizeof(vis));       if(dfs(i)) ans++;    }    return ans;}int main(){    int cas = 1;    while(scanf("%d%d%d",&n,&m,&C)&&(n+m+C)){        for(int i = 1;i <= C;i++) scanf("%d",a + i);        for(int i = 0;i < n;i++) G[i].clear();        for(int i = 0;i < m;i++){            int u,v,w;            scanf("%d%d%d",&u,&v,&w);            G[u].push_back(P(w,v));        }        dij(dis[0],0);        for(int i = 1;i <= C;i++) GG[i].clear();        for(int i = 1;i <= C;i++){            int u = a[i];            dij(dis[u],u);            for(int j = 1;j <= C;j++){                if(a[j] != u && dis[0][u] + dis[u][a[j]] == dis[0][a[j]]) GG[i].push_back(j + C);            }        }        printf("Case %d: %d\n",cas++,C - Maxmatch());    }    return 0;}