思路：动态规划

定义$dp[i][s]$表示到点$i$且花费为$s$的方案有多少。

那么对于通向点$i$的点集$v∈{V}$，有$dp[i][s+w_{v->i}]+=dp[v][s]$

最终答案为$dp[n][a]$

代码

Java

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int numVertices = scanner.nextInt(), numEdges = scanner.nextInt(), maxWeight = scanner.nextInt();
        
        // 用于存储图中的边
        List<int[]> edges = new ArrayList<>();
        for(int i = 0 ; i < numEdges ; i ++) {
            edges.add(new int[]{scanner.nextInt(), scanner.nextInt(), scanner.nextInt()});
        }

        // 按照边的权重从小到大排序
        edges.sort(Comparator.comparingInt(x -> x[2]));

        // 动态规划表，dp[i][j]表示从起点到达第i个顶点且总权重为j的路径数
        int[][] dp = new int[numVertices+1][maxWeight+1];
        dp[1][0] = 1;  // 初始状态，从起点1出发，权重为0的路径数为1

        // 用于标记是否存在多余模数的情况
        boolean[] overflowFlag = new boolean[numVertices+1];
        final int MODULO = 20220201;

        for(int weight = 0 ; weight < maxWeight ; weight ++) {
            for(int[] edge : edges) {
                if(weight + edge[2] > maxWeight) break;  // 超过最大权重，跳出循环

                dp[edge[1]][weight + edge[2]] += dp[edge[0]][weight];
                if(dp[edge[1]][weight + edge[2]] >= MODULO) {
                    dp[edge[1]][weight + edge[2]] -= MODULO;
                    overflowFlag[edge[1]] = true;  // 标记存在溢出
                }
            }
        }

        // 如果存在多余模数的情况，输出特定信息
        if(overflowFlag[numVertices]) System.out.println("All roads lead to Home!");
        
        // 输出到达终点n且权重为a的路径数
        System.out.println(dp[numVertices][maxWeight]);
    }
}

c++

#include<bits/stdc++.h>

using namespace std;

const int N = 105;
struct edge{
    int v, w;
};

int main(){
    int n, m, a;
    cin>>n>>m>>a;
    vector<edge>g[N];
    for(int i = 0; i < m; i ++){
        int u, v, w;
        cin>>u>>v>>w;
        g[u].push_back({v, w});
    }
    int dp[N][1005] = {0};
    bool st[N][1005];
    memset(st, false, sizeof st);
    dp[1][0] = 1;//到达节点i，花费为j的方案数
    for(int j = 0; j < a; j ++){
        for(int i = 1; i <= n; i ++){
            for(auto [v, w] : g[i]){
                if(j + w <= a){
                    dp[v][j + w] += dp[i][j];
                    if(dp[v][j + w] >= 20220201){
                        dp[v][j + w] %= 20220201;
                        st[v][j + w] = true;
                    }
                } 
            }
        }
    }
    if(st[n][a]) cout<<"All roads lead to Home!"<<endl;
    cout<<dp[n][a]<<endl;

    return 0;
}

java

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * @description:
 * @author：CatTail
 * @date: 2024/8/19
 * @Copyright: https://github.com/CatTailzz
 */
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), m = in.nextInt(), a = in.nextInt();
        List<int[]> edges = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            edges.add(new int[]{in.nextInt(), in.nextInt(), in.nextInt()});
        }
        // f[i][j] 表示走到i，恰好花费了j的方案数
        // 对于i能到达的点集k, 花费c，有f[k][j + c] += f[i][j]
        int[][] f = new int[n + 10][a + 10];
        f[1][0] = 1;
        int MOD = 20220201;
        boolean[] isModed = new boolean[n + 10];

        for (int w = 0; w <= a; w++) {
            for (int[] e : edges) {
                if (w + e[2] > a) {
                    continue;
                }
                f[e[1]][w + e[2]] += f[e[0]][w];
                if (f[e[1]][w + e[2]] >= MOD) {
                    f[e[1]][w + e[2]] %= MOD;
                    isModed[e[1]] = true;
                }
            }
        }
        if (isModed[n]) {
            System.out.println("All roads lead to Home!");
        }
        System.out.println(f[n][a]);
    }
}

题目描述

NN也是要回家过年的呢。

NN所在的国家有 n 座城市，m 条有向道路，第 i 条道路由城市$u_i$通往城市$v_i$，通行费为 $w_i$。

作为一头豪气的N，希望他回家的花费是一个特殊的数字(例如666元)。具体的说，NN希望从城市1移动到城市n，并恰好花费a元。

请你告诉NN，他有多少种回家的方案?

输入描述

第一行三个整数$n,m,a(1≤n≤100,1≤m≤1000,1≤a≤1000)$，含义如题面所示。 接下来$m$行，第$i$行三个整数 $u_i,v_i, w_i(1 ≤ u_i,v_i \le n,1≤ w_i ≤ a)$，描述了一条道路。

输出描述

如果NN回家的方家数大于等于 20220201种，请你在第一行输出All roads lead to Home!，然后在第二行输出回家的方案数对 20220201 取模的结里

否则只需要输出一行一个整数，表示NN回家的方案数。

样例

输入

3 6 2
1 2 1
1 2 1
1 2 1
2 3 1
2 3 1
2 3 1

输出

9

说明

从城市一到城市二有3种不同的走法，从城市二到城市三也有3种不同的走法，根据乘法原理我们可以知道，一共有3x3=9种不同的回家方法。