2018-05-24

题目大意：

给一张由非负边组成的图，（可能有零边），设从出发点1到终点n的路径的最短路为d，求出所有到达n的路径中，路程长度为d~d+k的方案总数。（取模）

若有无数条，输出-1；

分析：

暴力：

1.30分k=0，最短路计数暴力妥妥30分

2.70分，因为，k<=50，比较小，而n<=100000，所以是NK复杂度。

每个点的偏移量k可以由之前能到达这个点的小于等于k的值转过来，

所以设f[i][j]表示，在第i号点，距离到i号点最短路的偏移量为j的方案总数。也就是说，到i的路径长度为dis[i]+j的方案数。(dis[i]为从1到i最短路长度）

其中,j>=0&&j<=k

可以知道，从1-u-v和从1-v（路径都是最短路）相比较，偏移量就是：dis[u]+val[u,v]+j-dis[x]这么长。

发现，同一层之间可能有转移。

不能有后效性，那么转移顺序怎么处理？

发现，同一层之间有转移的话，必然是从dis小的到dis大的。

dis大的不可能转移到dis小的，并且偏移量不变。

所以对dis排序。

至于dis相同的，也不可能之间产生转移。随便排序就好了。

 

100分

但是刚才这个办法显然有坑。剩下的数据点，有0边。

先判断-1，发现，有0环，并且走0环可以是一条符合长度偏移量<=k的方案。

（但是我蒟蒻，没想这么多，直接判的零环，没想到过了。看来没有“有零环但不在方案数中”的测试点）

（所以代码其实有错，正解应该是判断0环上的是否存在一点x符合 dis1[x]+disn[x]<=dis[n]+k 这里，dis1表示从1出发最短路，disn表示从n出发最短路）

(这样才能保证走到0环后，随便走零边都是一种合法方案。而不是还没到0环就超过了k）

对于0链，a->b->c，w均为0，dis值是一样的，不能按dis值随便排了，必须先更新a,再b，再c。

所以，拓扑排序。专为0边准备。

把所有0边揪出来，判断-1的时候，也就进行了拓扑排序。

所以，现在，结点排序的优先级定义为：dis不同，dis小的优，否则拓扑序小的优。

spfa最短路。（有人用线段树，我太弱不会）

这个题，不开O2，洛谷还是要T两个点。很差。

但是换了LibreOJ就2000ms一个点AC了。看来luogu评测机还是比较慢。

估计CCF老爷机要卡爆了。就算考试想出正解，估计也就卡到70分了。

总结：spfa+拓扑+dp+卡常

代码：

#include
      
       #define num ch-'0'using namespace std;typedef long long ll;const int N=100000+10;const int M=200000+10;const int inf=(0x3f3f3f3f)*2;int n,m,K,p;int rd(){    int x=0;char ch;    while(!isdigit(ch=getchar()));    for(x=num;isdigit(ch=getchar());x=x*10+num);    return x;}struct node{    int nxt,to,val;}bian[M];struct zero{    int nxt,to;}e0[M];int has[N],tot;int hd[N],cnt1;//真正边 int pp[N],cnt3;//0边 int du[N];//度数 int dis[N];//最短路 int da[N];//最终的循环顺序da[i]表示排名为i的节点 int q[N*2],l,r;bool vis[N];bool flag=true;//零环bool ll f[N][52];//dp数组 int id[N];//拓扑序，主要是针对0边处理 void add1(int x,int y,int z){    bian[++cnt1].nxt=hd[x];    bian[cnt1].to=y;    bian[cnt1].val=z;    hd[x]=cnt1;}void add3(int x,int y)//建0边 {    e0[++cnt3].nxt=pp[x];    e0[cnt3].to=y;    pp[x]=cnt3;}bool jud()//判零环，这其实是错的。{    memset(vis,0,sizeof vis);    l=1;r=0;    for(int i=1;i<=n;i++)    {         if(du[i]==0) q[++r]=i;    }    while(l<=r)    {        int x=q[l++];        vis[x]=1;        for(int i=pp[x];i;i=e0[i].nxt)        {            int y=e0[i].to;            du[y]--;            if(du[y]==0) q[++r]=y;        }    }    for(int i=1;i<=n;i++)      id[q[i]]=i;    for(int i=1;i<=tot;i++)    {        if(vis[has[i]]!=1) return true;    }    return false;}void spfa()//最短路 {    memset(vis,0,sizeof vis);    for(int i=1;i<=n;i++) dis[i]=inf;    dis[1]=0;    vis[1]=1;    l=1;r=0;    q[++r]=1;    while(l<=r)    {        int now=q[l++];        vis[now]=0;        for(int i=hd[now];i;i=bian[i].nxt)        {            int y=bian[i].to;            if(dis[y]>dis[now]+bian[i].val)            {                dis[y]=dis[now]+bian[i].val;                if(!vis[y])                {                    vis[y]=1;                    q[++r]=y;                }            }        }    }}bool cmp(int x,int y){
    //排序，决定循环顺序     return dis[x]==dis[y]?id[x]
       
      

 

 upda：2018.11.5

之前太菜了。

这个代码可以不卡常直接AC：

#include
     
      #define reg register int#define il inline#define numb (ch^'0')using namespace std;typedef long long ll;const int N=100000+5;const int M=200000+5;int n,m,t;int k,mod;void rd(int &x){    char ch;x=0;    while(!isdigit(ch=getchar()));    for(x=numb;isdigit(ch=getchar());x=x*10+numb);}struct node{    int nxt,to;    int val;}e[2*M],bian[2*M];int hd[N],cnt1;int pre[N],cnt2;bool in[N];int du[N];int f[N][55];int d[N];int po[N];bool zero[N];bool vis[N];void add(int x,int y,int z){    e[++cnt1].nxt=hd[x];    e[cnt1].to=y;    e[cnt1].val=z;    hd[x]=cnt1;}void add_c(int x,int y){    bian[++cnt2].nxt=pre[x];    bian[cnt2].to=y;    pre[x]=cnt2;}int dis[N];int q[10*N],l,r;void spfa(){    l=1,r=0;    memset(vis,0,sizeof vis);    memset(dis,0x3f,sizeof dis);    dis[1]=0;//    f[1][0]=1;    q[++r]=1;    while(l<=r){        int x=q[l++];vis[x]=0;    //    cout<<" x "<
      
       <<" dis "<
       
        <
        
         dis[x]+e[i].val){                dis[y]=dis[x]+e[i].val;                //f[y][0]=f[x][0];                if(!vis[y]){                    vis[y]=1;                    q[++r]=y;                }            }        }    }}bool topo(){    l=1,r=0;    memset(po,0x3f,sizeof po);    memset(in,0,sizeof in);    for(reg i=1;i<=n;++i){        d[i]=i;        if(zero[i]&&du[i]==0){            q[++r]=i;        }    }    int lp=0;    while(l<=r){        int x=q[l++];        po[x]=++lp;    //    cout<<" xxx "<
         
          <
          
           =mod)?f[y][to]+f[x][o]-mod:f[y][to]+f[x][o]; } } } } ll ans=0; for(reg i=0;i<=k;++i){ ans=ans+f[n][i]; if(ans>=mod) ans-=mod; } printf("%lld\n",ans); } return 0;}