Luogu 1606 [USACO07FEB]白银莲花池Lilypad Pond

感觉应当挺简单的，但是弄了好久……菜死了

如果不考虑那些为$1$的点，直接跑个最短路计数就好了，但是我们现在有一些边可以不用付出代价，那么只要在连边的时候先预处理搜一下就好了。

原来的想法是拆点，但是这样子不好连边，所以直接把点权转化到边权上来。

注意到起点其实不用付出代价，那么最后的答案就是$dis_ed - 1$。

时间复杂度上界是$O(n^4 + n^2log(n^2))$。

Code：

#include <cstdio>

#include <cstring>

#include <queue>

using namespace std;

typedef long long ll;

typedef pair <ll, int> pin;

const int N = ;

const int M = 2e5 + ;

const int L = ;

const int dx[] = {-, -, -, -, , , , };

const int dy[] = {-, -, , , , , -, -};

const ll inf = 0x3f3f3f3f3f3f3f3f;

int n, m, a[L][L], tot = , head[N];

ll dis[N], cnt[N];

bool vis[N], ins[L][L];

struct Edge {

    int to, nxt;

} e[M];

inline void add(int from, int to) {

    e[++tot].to = to;

    e[tot].nxt = head[from];

    head[from] = tot;

}

template <typename T>

inline void read(T &X) {

    X = ; char ch = ; T op = ;

    for(; ch > '' || ch < ''; ch = getchar())

        if(ch == '-') op = -;

    for(; ch >= '' && ch <= ''; ch = getchar())

        X = (X << ) + (X << ) + ch - ;

    X *= op;

}

inline int id(int x, int y) {

    return (x - ) * m + y;

}

void dfs(int nowId, int x, int y) {

    ins[x][y] = ;

    for(int i = ; i < ; i++) {

        int tox = x + dx[i], toy = y + dy[i];

        if(tox <  || tox > n || toy <  || toy > m) continue;

        if(ins[tox][toy]) continue;

        if(a[tox][toy] == ) dfs(nowId, tox, toy);

        else ins[tox][toy] = , add(nowId, id(tox, toy));

    }

}

priority_queue <pin> Q;

void dij(int st) {

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

    cnt[st] = 1LL, dis[st] = 0LL;

    Q.push(pin(, st));

    for(; !Q.empty(); ) {

        int x = Q.top().second; Q.pop();

        if(vis[x]) continue;

        vis[x] = ;

        for(int i = head[x]; i; i = e[i].nxt) {

            int y = e[i].to;

            if(dis[y] > dis[x] + ) {

                dis[y] = dis[x] + ;

                cnt[y] = cnt[x];

                Q.push(pin(-dis[y], y));

            } else if(dis[y] == dis[x] + ) {

                cnt[y] += cnt[x];

            }

        }

    }

}

int main() {

//    freopen("testdata.in", "r", stdin);

    read(n), read(m);

    int st, ed;

    for(int i = ; i <= n; i++)

        for(int j = ; j <= m; j++) {

            read(a[i][j]);

            if(a[i][j] == ) st = id(i, j);

            if(a[i][j] == ) ed = id(i, j);

        }

    for(int i = ; i <= n; i++)

        for(int j = ; j <= m; j++)

            if(a[i][j] ==  || a[i][j] == ) {

                memset(ins, , sizeof(ins));

                dfs(id(i, j), i, j);

            }

    dij(st);

    if(dis[ed] == inf) puts("-1");

    else printf("%lld\n%lld\n", dis[ed] - , cnt[ed]);

    return ;

}