网站图片倒计时怎么做的,wordpress的网站好用吗,服务平台推广,中国咨询公司排名50强题意#xff1a;给一张帯权有向图#xff0c;求 111 到 nnn 长度不超过最短路长度 kkk 的路径条数 模 PPP。有无数条输出 −1-1−1 。 n≤105,m≤2105,k≤50n\leq 10^5,m\leq 2\times 10^5,k\leq 50n≤105,m≤2105,k≤50#xff0c;边权非负
先往最短路图想
发现 kkk 很小…题意给一张帯权有向图求 111 到 nnn 长度不超过最短路长度 kkk 的路径条数 模 PPP。有无数条输出 −1-1−1 。
n≤105,m≤2×105,k≤50n\leq 10^5,m\leq 2\times 10^5,k\leq 50n≤105,m≤2×105,k≤50边权非负
先往最短路图想
发现 kkk 很小考虑硬上 dp。
设 f(u,k)f(u,k)f(u,k) 表示从 uuu 到 nnn 多走 kkk 的路径数。
转移枚举下一步往哪里走。
f(u,k)∑(u,v)∈Ef(v,k−(w(u,v)disu−disv))f(u,k)\sum_{(u,v)\in E}f(v,k-(w(u,v)dis_u-dis_v))f(u,k)(u,v)∈E∑f(v,k−(w(u,v)disu−disv))
其中 disudis_udisu 为 111 到 uuu 最短路长度。
在没有零边的基础上右边这块 w(u,v)disu−disvw(u,v)dis_u-dis_vw(u,v)disu−disv 取 000 当且仅当 (u,v)(u,v)(u,v) 在最短路图上。因为这是个 DAG所以在最短路图上跑拓扑排序然后枚举 kkk 更新就可以了。这样可以拿到 707070 分的好成绩。
有零边时可能会出现 disnkdis_nkdisnk 内可达的零环这样答案为无穷大。如果拓扑排序后点 iii 入度不为 000 说明在零环上此时如果 disidisi′≤disnkdis_idis_i \leq dis_nkdisidisi′≤disnk 就输出 −1-1−1。dis′disdis′ 为到 nnn 的最短距离
否则的话反正都走不到这里直接把伪的拓扑序继续往后做。
复杂度 O(nlognnk)O(n\log nnk)O(nlognnk)
#include iostream
#include cstdio
#include cstring
#include cctype
#include algorithm
#include utility
#include queue
#define MAXN 100005
#define MAXM 200005
using namespace std;
int n,m,k,P;
inline int add(const int x,const int y){return xyP? xy-P:xy;}
inline int read()
{int ans0;char cgetchar();while (!isdigit(c)) cgetchar();while (isdigit(c)) ans(ans3)(ans1)(c^48),cgetchar();return ans;
}
struct edge{int u,v,w;}e[MAXM];
int head[MAXN],nxt[MAXM],cnt;
inline void addnode(int u,int v,int w)
{e[cnt](edge){u,v,w};nxt[cnt]head[u];head[u]cnt;
}
templatetypename T,typename cmplessT
struct heap
{T val[MAXM];T* end;heap(){endval;}inline bool empty(){return endval;}inline void push(const T v){*(end)v;push_heap(val,end,cmp());}inline T pop(){pop_heap(val,end,cmp());return *(--end);}
};
typedef pairint,int pi;
heappi,greaterpi q;
int dis[MAXN],disn[MAXN],deg[MAXN];
inline void dij(int* dis,int s1)
{memset(dis,0x3f,sizeof(disn));dis[s]0;q.push(make_pair(0,s));while (!q.empty()){int uq.pop().second;for (int ihead[u];i;inxt[i])if (dis[u]e[i].wdis[e[i].v])dis[e[i].v]dis[u]e[i].w,q.push(make_pair(dis[e[i].v],e[i].v));}
}
int lis[MAXN],vis[MAXN],tim;
void dfs(int u)
{vis[u]1;for (int ihead[u];i;inxt[i])if (dis[u]e[i].wdis[e[i].v]){deg[e[i].v];if (!vis[e[i].v]) dfs(e[i].v);}
}
inline void topsort()
{queueint q;tim0;q.push(1);while (!q.empty()){int uq.front();q.pop();lis[tim]u;for (int ihead[u];i;inxt[i])if (dis[u]e[i].wdis[e[i].v](--deg[e[i].v]0))q.push(e[i].v);}
}
int f[55][MAXN],u[MAXM],v[MAXM],w[MAXM];
int main()
{for (int Tread();T;T--){cnttim0;memset(head,0,sizeof(head));memset(nxt,0,sizeof(nxt));memset(deg,0,sizeof(deg));memset(vis,0,sizeof(vis));nread(),mread(),kread(),Pread();for (int i1;im;i) u[i]read(),v[i]read(),w[i]read(),addnode(v[i],u[i],w[i]);dij(disn,n);cnt0;memset(head,0,sizeof(head));memset(nxt,0,sizeof(nxt)); for (int i1;im;i) addnode(u[i],v[i],w[i]);dij(dis);dfs(1);topsort();int ans0;for (int i1;in;i) if (deg[i]dis[i]disn[i]dis[n]k) {puts(-1);goto end;}memset(f,0,sizeof(f));f[0][n]1;for (int t0;tk;t)for (int xtim;x1;x--){int ulis[x];for (int ihead[u];i;inxt[i]){int dele[i].w-dis[e[i].v]dis[u];if (tdel) f[t][u]add(f[t][u],f[t-del][e[i].v]);}}for (int i0;ik;i) ansadd(ans,f[i][1]);printf(%d\n,ans);end:;}return 0;
}
