noip2017d1t3

其实是参考洛谷上某篇题解的思路；

先求出两个dis数组表示从1走和从n走的最短路；

转移方程：dp[v][dis1[u]-dis1[v]+w+j]+=dp[u][j];

转移顺序要注意一下呢，肯定是先枚举第二维；

dis1[u]-dis1[v]+w+j>=j;

因为有等号，即有同层之间的转移，第一维也不能随便枚举；

如果没有0边，我们可以考虑按dis1从小到大枚举，和dijkstra很像，可以保证更新顺序是对的；

有了零边就要考虑连续好几个零边之间的转移，这个可以把0边挑出来拓扑排序；

关于-1的判断，把零边挑出来之后是可以知道那些点是在零环中的，再看一下经过这个点的路径有没有满足条件的就好了。

#include<iostream>

#include<cstring>

#include<cmath>

#include<cstdio>

#include<algorithm>

#include<queue>

using namespace std;

typedef long long ll;

const int maxn=;

const ll inf=1e12;

ll dp[maxn][],dis[maxn][];

struct edg{

    int nex,to;

    ll w;

}e[maxn*][];

struct node{

    int id;

    ll dis;

    bool operator<(const node&a)const{

        return dis>a.dis;

    }

}A,B;

int s,flag,head,tail,t1,t2,vis[maxn],last[maxn][],T,n,m,k,p,x,y,qq[maxn];

int h[maxn],pre[maxn*],other[maxn*],t3,du[maxn],tot,in[maxn];

ll z;

priority_queue<node>q;

void add3(int x,int y){++t3;pre[t3]=h[x];h[x]=t3;other[t3]=y;}

void add1(int x,int y,ll z){++t1;e[t1][].nex=last[x][];last[x][]=t1;e[t1][].to=y;e[t1][].w=z;}

void add2(int x,int y,ll z){++t2;e[t2][].nex=last[x][];last[x][]=t2;e[t2][].to=y;e[t2][].w=z;}

void dijkstra(int lei){

    //lei=0,1为起点,lei=1,n为起点；

    while(!q.empty())q.pop();

    memset(vis,,sizeof(vis));

    for(int i=;i<=n;++i)dis[i][lei]=inf;

    if(!lei)s=;else s=n;

    dis[s][lei]=;

    A.id=s;A.dis=;q.push(A);

    while(!q.empty()){

        B=q.top();q.pop();

        if(vis[B.id])continue;

        vis[B.id]=;

        for(int i=last[B.id][lei];i;i=e[i][lei].nex){

            int v=e[i][lei].to;

            if(vis[v])continue;

            if(dis[v][lei]>dis[B.id][lei]+e[i][lei].w){

                dis[v][lei]=dis[B.id][lei]+e[i][lei].w;

                A.id=v;A.dis=dis[v][lei];

                q.push(A);

            }

        }

    }

}

struct hehe{

    ll dis;

    int id,u;

    bool operator<(const hehe&a)const{

        if(dis==a.dis)return id<a.id;

        return dis<a.dis;

    }

}lj[maxn];

void tp(){

    for(int i=;i<=n;++i){

        lj[i].dis=inf;

        lj[i].id=;

    }

    flag=;

    head=tail=;

    for(int i=;i<=n;++i)if(in[i]&&!du[i]){

        qq[++tail]=i;lj[i].id=tail;

    }

    while(head<tail){

        int u=qq[++head];

        for(int i=h[u];i;i=pre[i]){

            int v=other[i];

            du[v]--;

            if(!du[v]){qq[++tail]=v;lj[v].id=tail;}

        }

    }

    for(int i=;i<=n;++i){

        if(in[i]&&du[i]){

            if(dis[i][]+dis[i][]<=dis[n][]+k){

                flag=;

            }

        }

    }

}

int main(){

    cin>>T;

    while(T--){

        scanf("%d%d%d%d",&n,&m,&k,&p);

        t1=t2=t3=;

        memset(last,,sizeof(last));

        memset(du,,sizeof(du));

        memset(in,,sizeof(in));

        memset(dp,,sizeof(dp));

        memset(h,,sizeof(h));

        for(int i=;i<=m;++i){

            scanf("%d%d%lld",&x,&y,&z);

            add1(x,y,z);add2(y,x,z);

            if(!z){add3(x,y);du[y]++;in[x]=in[y]=;}

        }

        dijkstra();

        dijkstra();

        tp();

        if(!flag){puts("-1");continue;}

        else{

            for(int i=;i<=n;++i){

                lj[i].dis=dis[i][];

                lj[i].u=i;

            }

            sort(lj+,lj+n+);

            dp[][]=;

            for(int j=;j<=k;++j)

              for(int i=;i<=n;++i)

              {

                  int u=lj[i].u;

                  for(int l=last[u][];l;l=e[l][].nex){

                      int v=e[l][].to;

                      if(dis[u][]-dis[v][]+e[l][].w+j<=k){

                        dp[v][dis[u][]-dis[v][]+e[l][].w+j]+=dp[u][j];

                        if(dp[v][dis[u][]-dis[v][]+e[l][].w+j]>=p)dp[v][dis[u][]-dis[v][]+e[l][].w+j]-=p;

                    }

                }

            }

            ll ans=;

            for(int i=;i<=k;++i){

                ans+=dp[n][i];

                if(ans>=p)ans-=p;

            }

            printf("%lld\n",ans);

        }

    }

    //system("pause");

    return ;

}

代码