如何做酒店网站设计,wordpress微信免签支付接口,wordpress-seo,app网站建站系统策划方案传送门 解法: 先不考虑0环 很容易想到dp 状态转移方程也很容易想到 设\(d[i]\)为n到i的最短路长度 当然此时是反向图 反向图是为了防止1能到达的点到达不了n而出错\(dp[i][j]\)表示到达i点距离为\(d[i]j\)的路径个数 则 x-y有路径 \(dp[x][k]dp[y][k-(d[y]edge(x,y)-d[x])]…传送门 解法: 先不考虑0环 很容易想到dp 状态转移方程也很容易想到 设\(d[i]\)为n到i的最短路长度 当然此时是反向图 反向图是为了防止1能到达的点到达不了n而出错\(dp[i][j]\)表示到达i点距离为\(d[i]j\)的路径个数 则 x-y有路径 \(dp[x][k]dp[y][k-(d[y]edge(x,y)-d[x])]\ (0\le d[y]edge(x,y)-d[x]\le k)\) 此时为正向图 当然dp在这种图中不好实现 改成记忆化搜索 若 有些点反向图n到达的了而正向图1到达不了 这些点在正向图搜索时不可能收到 而当 有些点反向图n到达不了而正向图1到达的了 这些点的d[]值为“正无穷” 此时\(d[y]edge(x,y)-d[x]\)要么小于0要么大于k 所以对答案也无影响 再考虑0环 若一次深搜时出现两次ij 那么一定有0环 想一想就知道了 这时输出-1结束就行 否则 最终答案就是 \(\sum_{i0}^kdp[1][i]\) 代码: 第一种:最好理解 前缀和在主程序中处理 但是评测姬一累就会凉凉 #includeiostream
#includecstdio
#includealgorithm
#includecstring
#includevector
#includecmath
#includequeue
#includemap
#define inf 2000000000
#define min(x,y) ((x)(y)?(x):(y))
#define max(x,y) ((x)(y)?(x):(y))
#define rep(i,a,b) for(register int i(a);i(b);i)
#define dwn(i,a,b) for(register int i(a);i(b);--i)
using namespace std;
typedef long long ll;
int T,n,m,k,mod,ans;
int d[100010],dp[100010][55];
int tot,head[100010],tt,rev[100010];
bool cmp,vis[100010],v[100010][55];
queueint que;
struct EDGE
{int to,nxt,d;
}edge[200010],reve[200010];
inline void add(int u,int v,int d)
{edge[tot].tov;edge[tot].dd;edge[tot].nxthead[u];head[u]tot;
}
inline void addr(int u,int v,int d)
{reve[tt].tov;reve[tt].dd;reve[tt].nxtrev[u];rev[u]tt;
}
inline int read()
{int x0;char chgetchar();while(ch0||ch9)chgetchar();while(ch0ch9){x(x3)(x1)(ch^48);chgetchar();}return x;
}
inline void spfa()
{d[n]0;que.push(n);while(!que.empty()){int xque.front();que.pop();vis[x]0;for(int irev[x];i;ireve[i].nxt){int yreve[i].to,disreve[i].d;if(d[y]d[x]dis){d[y]d[x]dis;if(!vis[y]) vis[y]1,que.push(y);}}}
}
int getdp(int x,int t)
{if(v[x][t]){v[x][t]0;cmp1;return 0;}if(dp[x][t]) return dp[x][t];v[x][t]1;for(int ihead[x];i;iedge[i].nxt){int yedge[i].to;int dist-(d[y]edge[i].d-d[x]);if(dis0||disk) continue;dp[x][t](dp[x][t]getdp(y,dis))%mod;if(cmp){v[x][t]0;return 0;}}v[x][t]0;if(xnt0) dp[x][t]1;//为了排除过终点的零环 终点初始值需要放在此处处理return dp[x][t];
}
int main()
{Tread();while(T--){nread(),mread(),kread(),modread();tot1,tt1;memset(head,0,sizeof(head));memset(rev,0,sizeof(rev));memset(d,0x3f,sizeof(d));memset(dp,0,sizeof(dp));rep(i,1,m){int uread(),vread(),dread();add(u,v,d);addr(v,u,d);}spfa();ans0,cmp0;dwn(i,k,0)ans(ansgetdp(1,i))%mod;if(cmp) printf(-1\n);else printf(%d\n,ans);}return 0;
}第二种:getdp()在一边跑一边处理前缀和 很快 #includeiostream
#includecstdio
#includealgorithm
#includecstring
#includevector
#includecmath
#includequeue
#includemap
#define inf 2000000000
#define min(x,y) ((x)(y)?(x):(y))
#define max(x,y) ((x)(y)?(x):(y))
#define rep(i,a,b) for(register int i(a);i(b);i)
#define dwn(i,a,b) for(register int i(a);i(b);--i)
using namespace std;
typedef long long ll;
int T,n,m,k,mod,ans;
int d[100010],dp[100010][55];
int tot,head[100010],tt,rev[100010];
bool cmp,vis[100010],v[100010][55];
queueint que;
struct EDGE
{int to,nxt,d;
}edge[200010],reve[200010];
inline void add(int u,int v,int d)
{edge[tot].tov;edge[tot].dd;edge[tot].nxthead[u];head[u]tot;
}
inline void addr(int u,int v,int d)
{reve[tt].tov;reve[tt].dd;reve[tt].nxtrev[u];rev[u]tt;
}
inline int read()
{int x0;char chgetchar();while(ch0||ch9)chgetchar();while(ch0ch9){x(x3)(x1)(ch^48);chgetchar();}return x;
}
inline void spfa()
{d[n]0;que.push(n);while(!que.empty()){int xque.front();que.pop();vis[x]0;for(int irev[x];i;ireve[i].nxt){int yreve[i].to,disreve[i].d;if(d[y]d[x]dis){d[y]d[x]dis;if(!vis[y]) vis[y]1,que.push(y);}}}
}
int getdp(int x,int t)
{if(v[x][t]){v[x][t]0;cmp1;return 0;}if(dp[x][t]) return dp[x][t];v[x][t]1;for(int ihead[x];i;iedge[i].nxt){int yedge[i].to;int dist-(d[y]edge[i].d-d[x]);if(dis0||disk) continue;dp[x][t](dp[x][t]getdp(y,dis))%mod;if(cmp){v[x][t]0;return 0;}}v[x][t]0;if(xn) dp[x][t]1;//对比第一种 其实就是此处改了 因为dp[1][k]-dp[n][i]与dp[1][k-i]-dp[n][0]所得值为相同的 所以给dp[n][]全部赋值为1 用一次getdp(1,k)即可过return dp[x][t];
}
int main()
{Tread();while(T--){nread(),mread(),kread(),modread();tot1,tt1;memset(head,0,sizeof(head));memset(rev,0,sizeof(rev));memset(d,0x3f,sizeof(d));memset(dp,0,sizeof(dp));rep(i,1,m){int uread(),vread(),dread();add(u,v,d);addr(v,u,d);}spfa();cmp0;ansgetdp(1,k);if(cmp) printf(-1\n);else printf(%d\n,ans);}return 0;
}转载于:https://www.cnblogs.com/MYsBlogs/p/11068548.html
