[NOIP2014]寻找道路

初探

本质是最短路，奈何加了最短路的点的出边必须直接或间接到达终点。

想法

先开始没有注意到条件，写了堆优化dij就交了。看到条件后想着反向建边加拓扑，发现很烦。并查集也寄了。

分解条件

出边直接或者间接到达终点，就是说出边的点只要和终点连通即可。

因此我先求一遍时候连通，然后再dfs求出边均连通。将连通转化为点值关系，正向求，会有反复入点的困难，就是出点需要入点，有很多环，越弄越解不开，于是反向建边。

从终点出发，出点 x，通过边走向 y，则将 y 加上一个度数，开始建边时计算一个度数，两度数相等且不为 0 ，则说明最短路可以走改边。

#include <bits/stdc++.h>

using namespace std;

/*
            ...,                                   ``  `  `   `    ` ``
          ,3,M#MN,                              `    ..   .   ..  `   ``
`` `` `  .` iJNNMM;                            ` ` ``.............    ``
``` `` ` ,x.?7MMr^`.  `           `       ` ``   `   ............... ` `
` ` ` ` `.Mc.^?Mb^.Je..`  ` ` `` ` ` ` ` `   ` `` .......^..^..........
```` ``` .Y6.^.dN^.MNMMNNa, ``      ` ` ` ` `  ``  ......^.^.^^.^.^..^..
````` .,`J.Qm,.`d+M#MNMMMMMN,`  `  `  `  ` ` `  `  ....^..^.^.^..^.^.^.^
``` ,TTb ,JMMMMNNMMMMMMMMMMMP  ` ```` `` `  ` ` ```..^..^.^^.^.^.^.^^.^^
.``...JMb.NkMMMMMMMMMMM#BUdM$````````   ` ` ````   .^.^..^.^^.^^..^..`.
`` ?N51JM.?MBHMMH#dNWHWNkHMMk.``     ``` ``   `` ..^.^.^.^^.^^.^^^.^^^^.
```.NHQgMy+JbZW@NZUWWWMMMMMMMN`  ` ``     ```  ..^..^...^.^^.^^..^^..^..
.````dMMMMmx.?;WM#0&dMMNMMMMMW    ```      ...^...^.^.^..^.^^.^.^.^.^...
````.MMMMrTMKC7TMHxudMMMMMMMNe``  ....^^....^..^.^..^^.^.^..^.^^.^.^.^^^
..`..dMMMl.dMBMMMMMMMMMMMMMMNl``  `..........^..^.^....^.^^..^.^.^...^^^
.`.`.MMMMMNNMMMMHNMMMNdBXMMMMMm, ` `   .^.^.^.^..^.^..^.^..^^..^..`....^
...dHMMMMMMMMMMMHNMMMHHbMMMMMMME.``  ``..^.^.^.^..^.^^..^.^.^^.` ` .^^^^
.,uMNJ&NNMMMMM#4MMMMM#^ ?7TUZVMMMb   ``` ......^.^.^..^..^.^..````.`^^.`
dNMMNMMMMMYT!` `,YM#=` `  `.uMMMM#b `    .^.^...^.^..^.^.^..^ ``````` ``
MMMMMMMMMr`` `  ` `    `  `  TMMMM#b.........^.^....^...^.^.. ``````````
MMM5+.MMMb `  `    `` `  ``  `,WMMM#p..^..^...^.^^.^.^..^.^^````````````
gajgN 3`MH,``` ``` `  `   .  ...?M#dNw..````^^^^.^^^^^^^^^^.````````.```
TMMMD`.MMNMp```    .............`1+ZMRG........`:^:::^:^:``.............
dZ=1Q,.MMNMMr..........`      ``` WNdMRh....`^::::::+``.................


                                                        ` .....
     `                                                `` .MNNB`
   `       `                                          `.jNNMt
       `                                            ` .MNN#!
                                                  ``.+NNMY
   `      `  `         `     `                    `.MNN#!`
     `           `                            ```.JNNND
       `                                      ` .MNN#'  `
   `       `               ` ` ` `` `` `` ` `  JNNMD  `  `
                        `  `` `` .............MNNM^` ` `
     `         ` ` ```  ...+gMNNNNNNNNNNNNNNNNMND   .MNgJ..` `` `
   `     `  `   ` ...gMNNNNNMMY9=7!`  ` ``.MNMM^  `,MNNNNNNMa,.` `
       `  ` ` ..&MNNNNNM#Y=` `         ` .NNND`   `   7WNNMNNNNm,  `
        `` ..MNNNMNNMY!``             `.MNNM^         ` .TMNNNNNNm  `
   ` `   .dNNNNNNM9!`              `  .NNN@``            ``MNMNMNNb`
    ```.MNNMNMNMD`                ` .dNNM=                `dNNMNNNM.`
      JNNNMNNNM' `               ` .NNM@``               ``dNNNNMN#
   ``JNNNMNNMM'               ```.dNNMt `             ``  .NNMNMNM^
    .NNNMNNNNN                  .MNMB`                 ` .NNMNNNM^` `
    .MNNNMNMNM,`  `       `` `.dNNM$              ```` .MNMNNNMY
   ` ?NMNNNNMNN,       `    `.MNN#!  `        `     .+NNNNNM#=
     `?MNNMNNNNMN,.` ``  ` .dNMMY`      `` `` ` ..gNNNNNM#=``
    `   ?HNNMNNNNNNNg,  ` .MNN#!`     ` ` ...gMNNMNNM#Y!``
         ` ?YMNMNNMN#!  .jNNMNJ.JJJ&ggNMNNNNNNNMBY=``
   `    `    `` ?7YY` `.MNNNNNNNNMNNMMMMY9T=!  `     `
                     .JNNMD
     `              .MNN#' `      `
   `       `    `` JNNMD
               ` .MNN#^  `
       `   ` `` JNMMD        `
   `         `.MNNM^
     `  `` ` .NNND     `
         ``.dNNM^`
   `   `  .NNND
        `?777^`              `
     `
*/

typedef pair<int, int> PII;

const int N = 10010, M = 200010;

int n, m, s, t;
int h[N], e[M], ne[M], idx;
bool vis[N];
int dist[N];
int in[N];
int in2[N];

void add(int a, int b) {
  e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

int dijkstra() {
  memset(dist, 0x3f, sizeof dist);
  dist[s] = 0;
  priority_queue<PII, vector<PII>, greater<PII> > pq;
  pq.push({0, s});
  while (!pq.empty()) {
    PII t = pq.top();
    pq.pop();// 忘记pop真的会谢。
    int d = t.first, u = t.second;
    if (vis[u]) continue;
    vis[u] = true;
    for (int i = h[u]; i != -1; i = ne[i]) {
      int v = e[i];
      if (dist[v] > d + 1) {
        dist[v] = d + 1;
        if (!vis[v]) {
          if (in[v] == in2[v]) pq.push({dist[v], v});// 如果从终点开始的入度跟全图的入度相等，则最短路可以包含该点。
        }
      }
    }
  }
  // for (int i = s; i <= t; i ++ ) printf("dist of %d : %d\n", i, dist[i]);
  return dist[t] == 0x3f3f3f3f ? -1 : dist[t];
}

// 先开始想并查集发现并没有什么用处。
/*
int fa_one[N];
int find(int x) {
  if (fa_one[x] != x) fa_one[x] = find(fa_one[x]);
  return fa_one[x];
}

void merge(int x, int y) {
  x = find(x), y = find(y);
  if (x != y) {
    fa_one[x] = y;
  }
}
*/

int vis_one[N];
void dfs_one(int x) {// dfs 求从终点出发给每个点加上的入度。
  for (int i = h[x]; i != -1; i = ne[i]) {
    int y = e[i];
    in2[y] ++ ;
    if (!vis_one[y]) {
      vis_one[y] = true;
      dfs_one(y);
    }
  }
}

void sol() {
  memset(h, -1, sizeof h);
  scanf("%d%d", &n, &m);
  for (int i = 0; i < m; i ++ ) {
    int a, b;
    scanf("%d%d", &a, &b);
    if (a != b) add(b, a), in[a] ++ ;// 反向建边，给 a 加上一个入度。
  }
  scanf("%d%d", &t, &s);
  
  vis_one[s] = true;
  dfs_one(s);
  // for (int i = 1; i <= n; i ++ ) printf("in 2 of %d : %d\n", i, in2[i]);
  // puts("");
  // for (int i = 1; i <= n; i ++ ) printf("in of %d : %d\n", i, in[i]);
  printf("%d\n", dijkstra());
}

int main() {
	sol();
	return 0;
}