NOIP2017D1T3解题报告

最短路（Dijksra）+拓扑排序+DP 本题的一大处理难点就是0环，首先明确一点，并非所有的0环都会造成出现无数条可行路径，因此我们需要先将所有可行的0边单独取出来判断。判断是否可行的方法为如果某条边连接的两个端点分别到起点和终点的距离加上此条边的长度小于等于起点到终点的最短路，说明通过该条路径存在答案，并判断其是否在以1为源的最短路上，将其加入到新图（即最短路边集）中去。由于保证边权值非负，因此所有可行的0边必然都在新图的边集中。对新图进行拓扑排序，若发现排序后仍存在入度不为0的点，则说明存在0环（非0环至少有一条边不会被加入新图）。 接下来就是DP。这里的DP方法比较~~玄学~~。想象一个（k+1)层的图，每一层图都代表不同增量的方案数，每层图都由最短路相连（保证不会使增量增加），而层与层之间则有非最短路的边联通。显然把这样一张图构造出来比较麻烦且时间长，因此我们直接枚举每一层图，首先按照拓扑序对该层图的方案数进行累加（防止遗漏），再按照增量大于0的边推出下面层的方案数（因为边权非负，所以增量不会减少），最后统计增量为0~k的第n个点的方案数之和即为答案。 ~~更多细节详见代码~~ ```cpp #include <stdio.h> #include <iostream> #include <algorithm> #include <cstring> #include <string> #include <cmath> #include <cstdlib> #include <queue> #include <vector> #include <map> using namespace std; struct node { int next, to, dis; };//链式前向星 const int maxn=110000, maxm=220000, maxd=1000000000; node sq[maxm]; struct heapnode { int u, d; bool operator < (const heapnode& a) const { return d>a.d; } }; priority_queue <heapnode> q; int n, m, k, p, tuopu[maxn], a[maxm], b[maxm], w[maxm], st[maxn], sumin[maxn], dp[maxn][70], f[maxn], g[maxn], head[maxn], cnt=0; void clearedge(int n) { cnt=0; for (int i=1; i<=n; i++) head[i]=0; } void addedge(int u, int v, int w) { sq[++cnt].next=head[u];//指向以u节点为出发点的前一条边的编号 sq[cnt].to=v; sq[cnt].dis=w; head[u]=cnt; } void dijkstra(int st, int *dist) { for (int i=1; i<=n; i++) dist[i]=maxd; dist[st]=0; q.push((heapnode){st, 0}); while (!q.empty()) { heapnode h=q.top(); q.pop(); int now=h.u, cost=h.d; if (dist[now]!=cost) continue; for (int i=head[now]; i; i=sq[i].next) { node e=sq[i]; if (dist[now]+e.dis<dist[e.to]) { dist[e.to]=dist[now]+e.dis; q.push((heapnode){e.to, dist[e.to]}); } } } } void tpsort() {//按照重新构建的最短路边集进行拓扑排序 int top=1; st[top]=1; int pos=0; while (top>0) { int now=st[top]; top--; tuopu[++pos]=now; for (int i=head[now]; i; i=sq[i].next) { sumin[sq[i].to]--; if (sumin[sq[i].to]==0) {top++; st[top]=sq[i].to;} } } } int main() { //freopen("park10.in", "r", stdin); int t; scanf("%d", &t); while (t--) { scanf("%d%d%d%d", &n, &m, &k, &p); clearedge(n); for (int i=1; i<=m; i++) { scanf("%d%d%d", &a[i], &b[i], &w[i]); addedge(a[i], b[i], w[i]); } dijkstra(1, f); clearedge(n); for (int i=1; i<=m; i++) addedge(b[i], a[i], w[i]); dijkstra(n, g); memset(sumin, 0, sizeof(sumin)); memset(tuopu, 0, sizeof(tuopu)); clearedge(n); for (int i=1; i<=m; i++) if (f[a[i]]+g[b[i]]+w[i]<=f[n]+k && f[a[i]]+w[i]==f[b[i]]) {//所有满足长度不超过最短路长度+k的最短路边集（在这些边上走不会影响当前路径超出长度的增量） addedge(a[i], b[i], 0); sumin[b[i]]++; } for (int i=1; i<=m; i++) w[i]=f[a[i]]+w[i]-f[b[i]];//重新定义w为走该条路的长度增量 tpsort(); bool flag=true; for (int i=1; i<=n; i++) if (sumin[i]) flag=false; if (!flag) {printf("%d\n", -1); continue;} //在重新构建的边集中包含了所有可能的0边（因为0边最短），而进行完一轮拓扑排序后，若还有点的入度不为0，则说明存在0环 //准备进行dp for (int i=1; i<=n; i++) for (int j=0; j<=k; j++) dp[i][j]=0; //dp[i][j]表示第i个点增量为j的路径总数 dp[1][0]=1; for (int j=0; j<=k; j++) {//由于路径增量是非降的，因此可由较短的路径增量向下推出更长的路径增量 for (int i=1; i<=n; i++) {//按照最短路边集遍历时应该按照拓扑序从前往后计数防止遗漏 int now=tuopu[i]; for (int x=head[now]; x; x=sq[x].next) dp[sq[x].to][j]=(dp[sq[x].to][j]+dp[now][j])%p; } //再遍历所有会导致增量增加的边，由于此时增量一定增加，对于本层的计数不造成影响，因此无所谓顺序 for (int i=1; i<=m; i++) if (j+w[i]<=k && w[i]) dp[b[i]][j+w[i]]=(dp[b[i]][j+w[i]]+dp[a[i]][j])%p; } int ans=0; for (int i=0; i<=k; i++) ans=(ans+dp[n][i])%p; printf("%d\n", ans); } return 0; } ```