menu ZigZagK的博客

正在努力加载中QAQ

[记忆化搜索]NOIP2017Day1【逛公园】题解
apps HHHOJ
local_offer 查看标签
comment 0 条评论
remove_red_eye 22 次访问

解题报告

吃我一记万年神坑。考场上我想到了 $f_{i,j}$ 表示到 $i$ 点比最短路多 $j$ 的方案数,但是我不会转移,写了玄学转移骗了60。

不会转移?记忆化搜索大法吼啊,令 $dis_i$ 表示 $1$ 到 $i$ 的最短路,那么:

$$ f_{i,k}=\sum_{(j,i)\in E}f_{j,k-(dis_j+w_{i,j}-dis_i)} $$

从 $f_{n,i}$ 开始搜索就行了。现在唯一的问题就是 $0$ 环,实际上就是在记忆化搜索的过程中某个状态出现了两次就说明出现了 $0$ 环。为了防止最短路为 $0$ 的特殊情况,可以刷一遍 $f_{n,K+1}$ 。

示例程序

我怕你卡Spfa结果你告诉我你卡Dijkstra?假的,我写萎了。

#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
#define fr first
#define sc second
#define mp make_pair
using namespace std;
const int maxn=100000,maxm=200000,maxk=50;

int te,n,m,K,MOD,f[maxn+5][maxk+5],dis[maxn+5],ans;
int E,lnk[2][maxn+5],nxt[(maxm<<1)+5],son[(maxm<<1)+5],w[(maxm<<1)+5];
int si;pair<int,int> Heap[maxm+5];bool vis[maxn+5][maxk+5],fl;

#define Eoln(x) ((x)==10||(x)==13||(x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    return (l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r))?EOF:*l++;
}
template<typename T> inline int readi(T &x){
    T tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    return lst=='-'?x=-tot:x=tot,Eoln(ch);
}
#define Add(ID,x,y,z) (son[++E]=(y),w[E]=(z),nxt[E]=lnk[ID][x],lnk[ID][x]=E)
#define Push(x) (Heap[++si]=(x),push_heap(Heap+1,Heap+1+si))
#define Pop() (pop_heap(Heap+1,Heap+1+si--))
inline void Dij(int s){
    memset(dis,63,sizeof(dis));dis[s]=0;si=0;Push(mp(0,s));
    while (si){
        int x=Heap[1].sc,y=-Heap[1].fr;Pop();while (si&&dis[x]<y) x=Heap[1].sc,y=-Heap[1].fr,Pop();
        for (int j=lnk[0][x];j;j=nxt[j]) if (dis[x]+w[j]<dis[son[j]]) dis[son[j]]=dis[x]+w[j],Push(mp(-dis[son[j]],son[j]));
    }
}
inline void AMOD(int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;}
int DP(int x,int k){
    if (!fl) return -1;if (~f[x][k]) return f[x][k];vis[x][k]=true;f[x][k]=0;
    for (int j=lnk[1][x];j;j=nxt[j]){
        int now=k-(dis[son[j]]+w[j]-dis[x]);if (now<0) continue;
        if (vis[son[j]][now]) return fl=false,-1;AMOD(f[x][k],DP(son[j],now));
    }vis[x][k]=false;return f[x][k];
}
int main(){
    for (readi(te);te;te--){
        readi(n);readi(m);readi(K);readi(MOD);E=0;memset(lnk,0,sizeof(lnk));
        for (int i=1,x,y,z;i<=m;i++) readi(x),readi(y),readi(z),Add(0,x,y,z),Add(1,y,x,z);
        Dij(1);memset(f,255,sizeof(f));memset(vis,0,sizeof(vis));f[1][0]=1;ans=0;fl=true;DP(n,1);
        for (int k=0;fl&&k<=K;k++) AMOD(ans,DP(n,k));if (!fl) puts("-1"); else printf("%d\n",ans);
    }return 0;
}
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!
名称不能为空
邮箱不能为空,请填写正确格式
网址请用http://或https://开头
评论不能为空
资瓷Markdown和LaTex数学公式
keyboard_arrow_up