当前位置: 代码迷 >> 综合 >> NOIP2017 逛公园 题解报告 【最短路 + 拓扑序 + dp】
  详细解决方案

NOIP2017 逛公园 题解报告 【最短路 + 拓扑序 + dp】

热度:51   发布时间:2023-12-25 05:07:18.0

题目描述

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

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

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

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

为避免输出过大,答案对PPP取模。

如果有无穷多条合法的路线,请输出?1。

输入输出格式

输入格式:

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

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

接下来MMM行,每行三个整数ai,bi,cia_i,b_i,c_iai?,bi?,ci?,代表编号为ai,bia_i,b_iai?,bi?的点之间有一条权值为 cic_ici?的有向边,每两个整数之间用一个空格隔开。

输出格式:

输出文件包含 TTT 行,每行一个整数代表答案。

输入输出样例

输入样例#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

说明

【样例解释1】

对于第一组数据,最短路为 3。 1 – 5, 1 – 2 – 4 – 5, 1 – 2 – 3 – 5 为 3 条合法路径。

【测试数据与约定】

对于不同的测试点,我们约定各种参数的规模不会超过如下

测试点编号   TTT    NNN    MMM    KKK    是否有0边
1 5 5 10 0
2 5 1000 2000 0
3 5 1000 2000 50
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%的数据, 1P109,1ai,biN,0ci10001 \le P \le 10^9,1 \le a_i,b_i \le N ,0 \le c_i \le 10001P109,1ai?,bi?N,0ci?1000

数据保证:至少存在一条合法的路线。



题解

考场上想到了dp,甚至写出了转移方程,但是由于时间紧迫没有进一步想得出转移顺序,最后交了最短路。。。QAQ
我们看K最大50,考虑一个关于K的dp

设f[u][j]表示到达u路径比到达u的最短路长j的方案数
那么对于一个f[u][j],u的所有边u -> v,有转移方程f[v][d[u] + j + w - d[v]] += f[u][j]
因为当前从1到v的路经长L = 1到u的路经长d[u] + j 加上 边权w,减去d[v]就得到比最短路多的部分
只要这个值不大于K,都可以转移

考虑转移顺序。
由最短路我们有d[v] <= d[u] + w
也就是说d[u] + w - d[v] + j >= j
由于等号的存在我们会产生同状态的转移,这个时候就要考虑转移的顺序
有两种情况:
1、沿着最短路转移
2、沿着0边转移
我们只要确保这两种情况中最靠前的节点先转移就好了
1、对于最短路,最靠前就是d最小的,按d排个序就好了
2、而0边呢,最靠前先转移你想到了什么?
对,拓扑排序:
我们单独用0边建图,跑一次拓扑排序给每个0点标上拓扑序

这样子我们对所有的点双关键字排序,第一关键字最短路,第二关键字拓扑序,因为只有0边两端存在d相等的情况,所以其他的点拓扑序赋什么值都无所谓
最后我们按照排序的顺序写状态转移就A啦~
附上我丑丑的代码:

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#define LL long long int
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define fo(i,x,y) for (int i = (x); i <= (y); i++)
#define Redge(u) for (int k = head[u]; k != -1; k = edge[k].next)
using namespace std;
const int maxn = 200005,maxm = 400005,maxk = 60,INF = 1000000000;
inline int read(){int out = 0,flag = 1;char c = getchar();while (c < 48 || c > 57) {if (c == '-') flag = -1; c = getchar();}while (c >= 48 && c <= 57) {out = out * 10 + c - 48; c = getchar();}return out * flag;
}
int N,M,K,P;
int dS[maxn],dT[maxn],f[maxn][maxk],inde[maxn],id[maxn];
bool vis[maxn],zer[maxn];
int head[maxn],nedge = 0,h[maxn],ne = 0;
struct EDGE{int to,w,next;}edge[maxm],e[maxm];
inline void build(int u,int v,int w){edge[nedge] = (EDGE) {v,w,head[u]}; head[u] = nedge++;e[ne] = (EDGE) {u,w,h[v]}; h[v] = ne++;if (!w) zer[u] = zer[v] = true,inde[v]++;
}
struct node{int u,d;};
inline bool operator <(const node& a,const node& b){return a.d > b.d;}
struct Node{int d,ti;}E[maxn];
inline bool cmp(const int& a,const int& b){return E[a].d == E[b].d ? E[a].ti < E[b].ti : E[a].d < E[b].d;}
void dijkstraS(){REP(i,N) dS[i] = INF,vis[i] = false;priority_queue<node> q;dS[1] = 0;q.push((node){1,dS[1]});node u; int to;while (!q.empty()){u = q.top();q.pop();if (vis[u.u]) continue;vis[u.u] = true;Redge(u.u)if (!vis[to = edge[k].to]){if (dS[to] >= dS[u.u] + edge[k].w){dS[to] = dS[u.u] + edge[k].w;q.push((node){to,dS[to]});}}}
}
void dijkstraT(){REP(i,N) dT[i] = INF,vis[i] = false;priority_queue<node> q;dT[N] = 0;q.push((node){N,dT[N]});node u; int to;while (!q.empty()){u = q.top();q.pop();if (vis[u.u]) continue;vis[u.u] = true;for (int k = h[u.u]; k != -1; k = e[k].next)if (!vis[to = e[k].to] && dT[to] > dT[u.u] + e[k].w){dT[to] = dT[u.u] + e[k].w;q.push((node){to,dT[to]});}}
}
bool tuopu(){queue<int> q;REP(i,N){id[i] = i;E[i].d = dS[i]; E[i].ti = 0;if (zer[i] && !inde[i]){q.push(i);}}int u,to,cnt = 0;while (!q.empty()){u = q.front();q.pop();E[u].ti = ++cnt;Redge(u) if (!edge[k].w){inde[to = edge[k].to]--;if (!inde[to]) q.push(to);}}REP(i,N) if (zer[i] && inde[i] && dS[i] + dT[i] <= dT[1] + K) {printf("-1\n");return false;}sort(id + 1,id + 1 + N,cmp);//REP(i,N) cout<<id[i]<<' ';cout<<endl;return true;
}
void solve(){dijkstraS();dijkstraT();//REP(i,N) cout<<f[i][0]<<' ';cout<<endl;if(!tuopu()) return;f[1][0] = 1;for (int j = 0; j <= K; j++)for (int i = 1; i <= N; i++){int u = id[i];Redge(u){int v = edge[k].to;if (dS[u] + j + edge[k].w - dS[v] <= K){f[v][dS[u] + j + edge[k].w - dS[v]] = (f[v][dS[u] + j + edge[k].w - dS[v]] + f[u][j]) % P;}}}int ans = 0;for (int i = 0; i <= K; i++) ans = (ans + f[N][i]) % P;printf("%d\n",ans);
}
void init(){int a,b,c;memset(f,0,sizeof(f));N = read(); M = read(); K = read(); P = read();ne = nedge = 0;REP(i,N) head[i] = h[i] = -1,inde[i] = 0,zer[i] = false;while (M--) {a = read(); b = read(); c = read(); build(a,b,c);}
}
int main()
{int T = read();while (T--){init();solve();}return 0;
}