学步园

这题看了超哥的代码之后一知半懂。大概知道是怎么实现的。其实就是BFS搜索路径，在广搜过程中dis数组维护最短的路径，而dp数组维护路径上有几只虫子和一个节点由几条路径共享。最后通过遍历n节点的dp数组来确定路径数。

源代码来自：http://acm.hust.edu.cn/vjudge/contest/viewSource.action?id=2091664

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <cmath>
#include <queue>
#include <stack>
#include <ctime>
using namespace std;

#define LL long long
#define ULL unsigned long long
#define mod 1000000007
#define eps 1e-8
#define MP make_pair

#define mxn 5005
#define mxe 2000005

int first[mxn], vv[mxe], nxt[mxe], e;
int dis[mxn], q[mxn], c[mxn], dp[mxn][55];

void add( int u, int v ) {
    vv[e] = v; nxt[e] = first[u]; first[u] = e++;
}

void bfs( int k ) {
    memset(dis, 0x3f, sizeof(dis));
    memset(dp, 0, sizeof(dp));
    int head = 0, tail = 0;
    dis[1] = 0;
    dp[1][c[1]] = 1;
    q[tail++] = 1;
    while( head < tail ) {
        int u = q[head++];
        for( int j = 0; j <= k; ++j ) if( dp[u][j] )
        for( int i = first[u]; i != -1; i = nxt[i] ) {
            int v = vv[i];
            if( dis[v] == 0x3f3f3f3f ) q[tail++] = v;
            if( dis[v] >= dis[u] + 1 ) {
                dis[v] = dis[u] + 1;
                dp[v][j+c[v]] += dp[u][j];
            }
        }
    }
}

int main()
{
    //ios_base::sync_with_stdio(false);
    int n, m, k, u, v;
    while( scanf( "%d%d%d", &m, &n, &k ) != EOF ) {
        memset(first, -1, sizeof(first)); e = 0;
        for( int i = 1; i <= n; ++i ) {
            scanf( "%d%d", &u, &v );
            c[u] = v;
        }
        for( int i = 1; i <= m; ++i ) {
            scanf( "%d%d", &u, &v );
            add(u, v); add(v, u);
        }
        bfs(k);
        LL ans = 0;
        for( int i = 0; i <= k; ++i ) ans += dp[n][i];
        if( ans == 0 ) puts( "Impossible!" );
        else printf( "%lld\n", ans );
    }
    return 0;
}