Nearest Opposite Parity
题意:给定序列a[],每个a[i]代表到达这点是可以跳转至i+a[i]和i-a[i],要求求出每个点出发,至少要跳转几次才能使跳转后的点a[j]和这个点a[i]奇偶性不同。
思路:这里就是设两个超级源点,超级源点是最短路里面衍生出来的技巧,不知道可以点这个看,一个连接所有偶数,一个连接所有奇数,然后这些数之间,反向建边,比如从奇数点出发,那么从超级奇数点到任何一个偶数点的最短距离都代表他所能到某一个奇数点最短距离(反向思维).所以过程就是分别建立两个超级源点,可以一个下标0,一个下标n+1,然后把0指向所有偶数点,n+1指向所有奇数点,数之间反向建边,然后就是分别求0出发的最短路和n+1出发的最短路,用spfa和dijkstra都行。