传送门
花了一个下午才 A 的毒瘤题
思路：
这题需要建两个图，一个正向图，一个反向图。
先在正向图上跑一遍 dijkstar ，计算出每个点到 点1 的最短路径 。
然后在反向图上开始记忆化搜索：
- 和动规一样，先定义 f [ i ][ j ] 表示：从 点 1 到 点 i 的距离为 dis [ i ] + j 的方案数。（初始值要为负，不然判断 0环 的时候会出错）
- 对于每一条反向边（u，v，w）都有 f [ u ][ d ] = ∑ f [ u ][（dis[ u ] + d）-（dis[ v ] + w）] 。
设 lck_dis = （dis[ u ] + d）-（dis[ v ] + w）。
仔细分析会发现 lck_dis 就表示 点 u 到 起点 1 的距离。
这类似于 最短路计数 的转移，因为建的是反向边，所以要从后往前转移。
- 为了判断是否有毒瘤的 0边，需要开一个布尔数组 flag [ i ][ j ] 判断 dp 值是否被经过 2 次，且没有被确定，那么一定是有 0边 导致的自环。
Code:
#include<iostream> #include<cstdio> #include<cmath> #include<algorithm> #include<cstring> #include<cstdlib> #include<string> #include<stack> #include<vector> #include<queue> #include<deque> #include<map> #include<set> using namespace std; #define INF 0x3f const int maxn=1e5+7; inline int read() { int xs=0,kr=1; char ls; ls=getchar(); while(!isdigit(ls)) { if(ls=='-') kr=-1; ls=getchar(); } while(isdigit(ls)) { xs=(xs<<1)+(xs<<3)+(ls^48); ls=getchar(); } return xs*kr; } int T,n,m,k,p; long long ans; int head_dij[maxn],head_dfs[maxn],dis[maxn],f[maxn][61]; bool bo,vis[maxn],flag[maxn][61]; priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q; struct hh { int nex,to,w; } t_dij[maxn<<1],t_dfs[maxn<<1]; inline void clear() { bo=false; memset(head_dij,0,sizeof(head_dij)); memset(head_dfs,0,sizeof(head_dfs)); memset(dis,INF,sizeof(dis)); memset(vis,false,sizeof(vis)); memset(f,-1,sizeof(f)); } inline void add(int cnt,int nex,int to,int w) { t_dij[cnt].to=to; t_dij[cnt].w=w; t_dij[cnt].nex=head_dij[nex]; head_dij[nex]=cnt; t_dfs[cnt].to=nex; t_dfs[cnt].w=w; t_dfs[cnt].nex=head_dfs[to]; head_dfs[to]=cnt; } inline void dijkstra(int s) { dis[s]=0; q.push(make_pair(0,s)); while (!q.empty()) { int u=q.top().second; q.pop(); if (vis[u]) continue; vis[u]=true; for (int i=head_dij[u];i;i=t_dij[i].nex) { int v=t_dij[i].to,w=t_dij[i].w; if (!vis[v]&&dis[v]>dis[u]+w) { dis[v]=dis[u]+w; q.push(make_pair(dis[v],v)); } } } } int dfs(int u,int d) { if (flag[u][d]) { bo=true; return 0; } if (~f[u][d]) return f[u][d]; flag[u][d]=true;f[u][d]=0; for (int i=head_dfs[u];i;i=t_dfs[i].nex) { if(bo) break; int v=t_dfs[i].to,w=t_dfs[i].w; int lck_dis=(dis[u]+d)-(w+dis[v]); if (lck_dis>=0) f[u][d]=(f[u][d]+dfs(v,lck_dis))%p; } flag[u][d]=false; if (u==1&&!d) return ++f[u][d]; return f[u][d]; } int x,y,z; int main() { //freopen("park.in","r",stdin); //freopen("park.out","w",stdout); T=read(); while (T--) { clear(); n=read();m=read();k=read();p=read(); for(int i=1;i<=m;i++) { x=read();y=read();z=read(); add(i,x,y,z); } dijkstra(1); ans=dfs(n,0)%p; for(int i=1;i<=k;i++) { if(bo) break; ans=(ans+dfs(n,i))%p; } if(bo) printf("-1 "); else printf("%lld ",ans); } return 0; }
注：在 dfs 中，if ( ~ f [ u ][ d ] ) ⇔ if ( f [ u ][ d ] ≥ 0 ) 。有助于卡常