2018.11.01 낙곡P3953 공원구경(최단로+dp)
#include
using namespace std;
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
const int N=1e5+5,M=2e5+5;
int d[N],T,n,m,k,mod,first[N],cnt=0,ans,flag,f[55][N],dis[N];
bool in[55][N],vis[N];
struct edge{int v,w,next;}e[M<<1];
inline void add(int u,int v,int w){e[++cnt].v=v,e[cnt].w=w,e[cnt].next=first[u],first[u]=cnt;}
inline void spfa(){
queue<int>q;
dis[1]=0,vis[1]=1,q.push(1);
while(!q.empty()){
int x=q.front();
q.pop(),vis[x]=0;
for(int i=first[x];i;i=e[i].next){
int v=e[i].v;
if(dis[v]>dis[x]+e[i].w){
dis[v]=dis[x]+e[i].w;
if(!vis[v])vis[v]=1,q.push(v);
}
}
}
}
inline int dfs(int p,int d){
if(flag)return 0;
if(in[d][p])return flag=1,0;
if(~f[d][p])return f[d][p];
in[d][p]=1,f[d][p]=(p==n&&d<=k);
for(int i=first[p];i;i=e[i].next){
int v=e[i].v,dist=dis[p]+e[i].w+d-dis[v];
if(dist<0||dist>k)continue;
f[d][p]+=dfs(v,dist);
if(f[d][p]>=mod)f[d][p]-=mod;
}
return in[d][p]=0,f[d][p];
}
int main(){
T=read();
while(T--){
n=read(),m=read(),k=read(),mod=read();
memset(first,0,sizeof(first)),memset(dis,127,sizeof(dis)),memset(f,-1,sizeof(f)),memset(in,0,sizeof(in));
flag=ans=cnt=0;
for(int i=1,u,v,w;i<=m;++i)u=read(),v=read(),w=read(),add(u,v,w);
spfa(),ans=dfs(1,0),printf("%d
",flag?-1:ans);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Rails Turbolinks를 페이지 단위로 비활성화하는 방법원래 Turobolinks란? Turbolinks는 링크를 생성하는 요소인 a 요소의 클릭을 후크로 하고, 이동한 페이지를 Ajax에서 가져옵니다. 그 후, 취득 페이지의 데이터가 천이 전의 페이지와 동일한 것이 있...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.