逛公园

##Luogu##

题目描述

ShortestPath DynamicProgramming
NOIP 2017 D1T3
策策同学特别喜欢逛公园。公园可以看成一张$N$个点$M$条边构成的有向图，且没有自环和重边。其中$1$号点是公园的入口，$N$号点是公园的出口，每条边有一个非负权值，代表策策经过这条边所要花的时间。

策策每天都会去逛公园，他总是从1号点进去，从$N$号点出来。

策策喜欢新鲜的事物，它不希望有两天逛公园的路线完全一样，同时策策还是一特别热爱学习的好孩子，它不希望每天在逛公园这件事上花费太多的时间。如果1号点到$N$号点的最短路长为dd，那么策策只会喜欢长度不超过$d + K$的路线。

策策同学想知道总共有多少条满足条件的路线，你能帮帮它吗？

为避免输出过大，答案对$P$取模。

如果有无穷多条合法的路线，请输出$−1$。

输入输出格式

输入格式

第一行包含一个整数$T$,代表数据组数。

接下来$T$组数据，对于每组数据：第一行包含四个整数$N,M,K,P$每两个整数之间用一个空格隔开。

接下来$M$行，每行三个整数$a_i,b_i,c_i$，代表编号为$a_i,b_i$的点之间有一条权值为$c_i$的有向边，每两个整数之间用一个空格隔开。

输出格式

输出文件包含$T$行，每行一个整数代表答案。

输入输出样例

输入样例#1

2
5 7 2 10
1 2 1
2 4 0
4 5 2
2 3 2
3 4 1
3 5 2
1 5 3
2 2 0 10
1 2 0
2 1 0

输出样例#1

3
-1

说明

样例一说明
对于第一组数据，最短路为$3$。 $1 – 5$, $1 – 2 – 4 – 5$, $1 – 2 – 3 – 5$为$3$条合法路径。
测试数据与约定
对于不同的测试点，我们约定各种参数的规模不会超过如下

测试点编号	$T$	$N$	$M$	$K$	是否有0边
1	5	5	10	0	否
2	5	1000	2000	0	否
3	5	1000	2000	0	否
4	5	1000	2000	50	否
5	5	1000	2000	50	否
6	5	1000	2000	50	是
7	5	100000	200000	0	否
8	3	100000	200000	50	否
9	3	100000	200000	50	是
10	3	100000	200000	50	是

对于100%的数据,$ 1 \le P \le 10^9,1 \le a_i,b_i \le N ,0 \le c_i \le 1000$
数据保证：至少存在一条合法的路线。

示例代码

#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;

struct Path
{
    int from;
    int to;
    int length;
};

struct Node
{
    vector<Path> ways;
    vector<Path> backways;
    int dis = 2147483647;
    //初始化dis为最大
};

vector<Node> park;
//存图
vector<bool> inqueue;
//spfa中判断是否在队列中
int n_node, n_side, range, modnum;
//四个全局变量,点个数,边个数,范围,取模的数

struct cmp
{
    bool operator()(int a, int b)
    {
        return park[a].dis > park[b].dis;
        //这个cmp用于priority_queue的排序
    }
};

void getdata()
{
    cin >> n_node >> n_side >> range >> modnum;
    Node node;
    vector<Node> a(n_node + 1, node);
    //初始化n_node个点
    park = a;
    a.clear();
    vector<bool> b(n_node + 1, false);
    //初始化所有点不在队列中
    inqueue = b;
    b.clear();
    for (int i = 0; i < n_side; i++)
    {
        int f, t, v;
        cin >> f >> t >> v;
        Path s;
        s.length = v;
        s.from = f;
        s.to = t;
        park[f].ways.push_back(s);
        //添加正向边
        park[t].backways.push_back(s);
        //添加反向边
    }
}

priority_queue<int, vector<int>, cmp> p_queue;
//用于优化spfa的队列

void spfa()
{
    p_queue.push(1);
    park[1].dis = 0;
    inqueue[1] = true;
    //三句初始化，源点入队
    while (!p_queue.empty())
    {
        int now = p_queue.top();
        p_queue.pop();
        //取出点
        inqueue[now] = false;
        //当前点不再在队列中了
        for (unsigned int i = 0; i < park[now].ways.size(); i++)
        //遍历每一个出度
        {
            int next = park[now].ways[i].to;
            int value = park[now].ways[i].length;
            //取出数据
            if (park[next].dis > park[now].dis + value)
            //如果当前点通向下一个点的路径比当前更短
            {
                park[next].dis = park[now].dis + value;
                //赋值为最小
                if (!inqueue[next])
                //如果不再队列
                {
                    p_queue.push(next);
                    //入队
                    inqueue[next] = true;
                    //现在在队列中了
                }
            }
        }
    }
    return;
}

bool visiting[100001][51];
//是否正在访问
int paths[100001][51];
//对应每一个节点和剩余边长数

int dp(int root, int range_left)
{
    int ans = 0;

    if (range_left < 0 || range_left > range)
        return 0;
    //如果越界返回0

    if (visiting[root][range_left])
    {
        visiting[root][range_left] = false;
        return -1;
    }
    //如果存在0环(再次访问)则返回-1

    if (paths[root][range_left] != -1)
        return paths[root][range_left];
    //如果答案已经求出则返回

    visiting[root][range_left] = true;
    //表示正在进行访问

    for (unsigned int i = 0; i < park[root].backways.size(); i++)
    //
    {
        Path front = park[root].backways[i];
        //取出每一个入度

        int val = dp(front.from, range_left - front.length + park[root].dis - park[front.from].dis);
        //originalDis = park[root].dis - park[front.from].dis表示原来边的差距
        //diffience = originalDis - front.length表示两条边之间的差距
        //new_range_left = range_left + diffience相减就是新的剩余边长

        if (val == -1)
        {
            visiting[root][range_left] = false;
            return -1;
        }
        //如果存在0环就继续向上返回-1

        ans = (ans + val) % modnum;
        //每次相加取模
    }
    visiting[root][range_left] = false;
    //当前点不再在队列中了

    if (root == 1 && range_left == 0)
        ans++;
    //访问到源点时候刚好结束
    //其实可以写成ans = 1;

    paths[root][range_left] = ans;
    //动规赋值

    return ans;
    //向上返回
}

int findway()
{
    int ans = 0;
    memset(paths, -1, sizeof(paths));
    //赋值为所有路径可能-1

    for (int i = 0; i <= range; i++)
    //枚举<=范围上限的每一种情况
    {
        int val = dp(n_node, i);
        if (val == -1)
            return -1;
        //如果有一个0环就没有继续递归的必要了
        ans = (ans + val) % modnum;
        //每次相加取模
    }
    return ans;
}

int main()
{
    ios::sync_with_stdio(false);
    //加速读取的常规操作
    int k_;
    cin >> k_;
    while (k_--)
    {
        getdata();
        //获取数据
        spfa();
        //求最短路径
        cout << findway() << endl;
        //找路径个数
    }
    return 0;
}