洛谷3953 NOIP2017 逛公园

$$ \text{考虑记忆化搜索} \\ \text{设}dis_u\text{表示从}u\text{到终点的最短距离} \\ \text{记录状态为}f\left( u,k \right) \text{表示从点}u\text{出发，到终点距离不超过}dis_u+k\text{的方案数} \\ \text{边界条件：} \\ \text{走到终点时，不管}k\text{是多少，方案数都会}+\text{1，同时继续向下搜索} \\ \text{要试图遍历一个已经在栈中的状态的时候说明走到了零环（零环上最短路不会变化）} \\ \text{转移的时候，对于一条边}\left( u,v,w \right) \ \text{考虑如果走这条边，我们比最短路又远了多少（肯定不会比最短路近）} \\ \text{首先如果}\left( u,v,w \right) \text{这条边在一条最短路上，那么显然满足}dis_v+w=dis_u\text{即}dis_v+w-dis_u=0 \\ \text{如果这条边不在最短路上，就说明走了这条边，到终点一定会花费比最短路更长的距离} \\ \text{即满足}x=dis_v+w-dis_u>0 \\ \text{这个时候如果走了这条边，那么我们就离最短路又远了}x\text{，所以，}f\left( u,k \right) \text{中可以直接} \\ \text{统计上}f\left( v,k-x \right) \\ \text{最后的答案为}f\left( \text{1,}k \right) $$

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <inttypes.h>
#include <queue>
#include <functional>
#include <cstring>
#define debug(x) std::cout << #x << " = " << x << std::endl;

typedef long long int int_t;

using std::cin;
using std::endl;
using std::cout;

const int_t LARGE = 100000;
const int_t INF = 0x7fffffff;
struct Processor{
	struct Edge{
		int_t to;
		int_t weight;
		Edge(int_t to,int_t weight){
			this -> to = to;
			this -> weight = weight;
		}
	};
	struct Pair{
		int_t dis;
		int_t vertex;
		Pair(int_t dis,int_t vtx){
			this -> dis = dis;
			this -> vertex  = vtx;
		}
		bool operator <(const Pair& x) const{
			return dis < x.dis; 
		}
		bool operator > (const Pair& x) const{
			return dis > x.dis;
		}
	};
	std::vector<Edge> graph[LARGE + 1];
	std::vector<Edge> rgraph[LARGE + 1];
	bool visited[LARGE + 1][51];
	bool visiting[LARGE + 1][51];
	int_t memory[LARGE + 1][51];
	int_t dis[LARGE + 1];
	int n,m,k,p;
	void pushEdge(int_t from,int_t to,int_t weight){
		graph[from].push_back(Edge(to,weight));
		rgraph[to].push_back(Edge(from,weight));
	}
	int_t search(int_t vtx,int_t k){
		if(k < 0) return 0;
//		cout<<"searching "<<vtx<<" "<<k<<" "<<endl;
		if(visited[vtx][k]) return memory[vtx][k];
		if(visiting[vtx][k]) return -1;
		visiting[vtx][k] = true;
		int_t result = 0;
		if(vtx == n) result = 1;
		for(int_t i = 0 ;i < graph[vtx].size(); i ++){
			Edge& curr = graph[vtx][i];
			int_t x = search(curr.to,k - (dis[curr.to] + curr.weight - dis[vtx]));
			if(x == -1){
				result = -1;
				break;
			}
			result = result + x;
			result %= p;
		}
		visited[vtx][k] = true;
		visiting[vtx][k] = false;
		return memory[vtx][k] = result;
	}
	int_t process(){
		static bool visited[LARGE + 1];
		memset(visited,0,sizeof(visited));
		memset(visiting,0,sizeof(visiting));
		scanf("%d%d%d%d",&n,&m,&k,&p);
		std::fill(dis + 1 ,dis + 1 + n,INF);
		std::fill(visited + 1 ,visited + 1 + n,false);
		
		for(int_t i = 1; i <= m;i++){
			int from,to,weight;
			scanf("%d%d%d",&from,&to,&weight);
			pushEdge(from,to,weight);
		}	
		dis[n]  = 0;
		std::priority_queue<Pair,std::vector<Pair>,std::greater<Pair> > heap;
		heap.push(Pair(0,n));
		while(heap.empty() == false){
			Pair top =  heap.top();
			heap.pop();
			if(visited[top.vertex]) continue;
			visited[top.vertex] = true;
			for(int_t i = 0;i< rgraph[top.vertex].size();i ++){
				Edge& curr = rgraph[top.vertex][i];
				if(dis[curr.to] > dis[top.vertex] + curr.weight){
					dis[curr.to] = dis[top.vertex] + curr.weight;
					heap.push(Pair(dis[curr.to],curr.to));
				}
			}
		}
		return search(1,k);
//		for(int_t i = 1;i <= n;i++){
//			cout<<"dis "<<i<<" = "<<dis[i] << endl;
//		}
	}
};

int main() {
	int T;
	scanf("%d",&T);
	for(int_t i = 1;i <= T;i++){
		Processor * p =new Processor;
		cout << p->process() << endl;
		delete p;
	}
    return 0;
}