这个题似曾相识啊，以前是用搜索剪枝+0/1边权bfs做的(题面可以参照上一篇这个题的博客)。

    有一类问题就是求 包含若干关键点的最小强联通子图大小是多少。

    如果关键点数量是变量，那么就是NP问题了。。。

    对于本题来说，关键点数量=2，就可以直接dp啦。

 

    设一个走正向边的点p和一个走逆向边的点q，f[i][j] 即是 p在i且q在j最少经过的点数，转移的话把去的路径伸直然后在纸上画一画，发现总共有三种：

1.i向后扩展一个点

2.j向后扩展一个点

3.i,j通过i到j的最短路径互换位置。

    因为状态图并不是dag，所以跑个dij就可以了。

 

#include
     
      #define ll long longusing namespace std;const int N=205;#define pb push_backint n,m,f[N][N],ans,to[N*2];int ne[N*2],hd[N],num,d[N][N];bool v[N][N];struct node{    int x,y;    bool operator <(const node &u)const{    	return f[x][y]>f[u.x][u.y];	}};priority_queue
      
        q;inline void add(int x,int y){ to[++num]=y,ne[num]=hd[x],hd[x]=num;}inline void solve(){	for(int i=1;i<=n;i++) d[i][i]=0;	for(int k=1;k<=n;k++)	    for(int i=1;i<=n;i++)	        for(int j=1;j<=n;j++) if(d[i][k]+d[k][j]