好神啊。。。

考虑维护d[i][j]表示st到i需要经过j个为x的边的最短路，这个就是分层图的最短路了

然后就可以发现，y=kx+b其中k=j，b=d[i][j]，有很多直线，然后我们要的就是一个单增的上凸包

这个直线最多只有n条，因为一个点经过多次肯定就是有环，那么一定不优

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;typedef long long LL;const int _=1e2;const int maxn=5*1e2+_;const int maxm=1e4+_;const double eps=1e-8;struct node{ int x,y,next;LL d;}a[maxm];int len,last[maxn];void ins(int x,int y,LL d){ len++; a[len].x=x;a[len].y=y;a[len].d=d; a[len].next=last[x];last[x]=len;}//----------------------------------------------def---------------------------------------------------------int n,st,ed;struct dij{ int x,c;LL d; dij(){} dij(int X,int C,LL D){x=X,c=C,d=D;} friend bool operator >(dij d1,dij d2){ return d1.d>d2.d;} friend bool operator <(dij d1,dij d2){ return d1.d
            
             < dij,vector
             
              ,greater
              
                >q;int mc; LL d[maxn][maxn]; bool v[maxn][maxn];//不可能跑环（不优），所以只需要点数步 void dijkstra(){ memset(d,63,sizeof(d));d[st][0]=0; memset(v,false,sizeof(v)); q.push(dij(st,0,d[st][0])); while(!q.empty()) { dij tno=q.top();q.pop(); int x=tno.x,c=tno.c; if(x==ed)mc=max(mc,c); if(v[x][c]==true)continue; v[x][c]=true; for(int k=last[x];k;k=a[k].next) { int y=a[k].y; if(a[k].d<0) { if(d[y][c+1]>d[x][c]&&c
               
                d[x][c]+a[k].d) { d[y][c]=d[x][c]+a[k].d; q.push(dij(y,c,d[y][c])); } } } }}//----------------------------------------------dij---------------------------------------------------------//系数k: 0~n: d值double getx(int i,int j){ return double(d[ed][j]-d[ed][i])/double(i-j);}LL gg(int i,int j)//i管理的范围的后界 { double x=getx(i,j); if(fabs(double(x)-double(int(x)))<=eps)x-=0.5; return int(floor(x));}int top,sta[maxm];char ss[10];int main(){ freopen("a.in","r",stdin); freopen("a.out","w",stdout); int m,x,y,dd; scanf("%d%d",&n,&m); len=1; for(int i=1;i<=m;i++) { scanf("%d%d%s",&x,&y,ss+1); if(ss[1]=='x')ins(x,y,-1); else { int sslen=strlen(ss+1); dd=0;for(int i=1;i<=sslen;i++)dd=dd*10+ss[i]-'0'; ins(x,y,dd); } } int Q; scanf("%d",&Q); while(Q--) { scanf("%d%d",&st,&ed); mc=-1;dijkstra(); if(mc==-1)puts("0 0"); else if(d[ed][0]==d[0][0])puts("inf"); else { top=1;sta[top]=0; for(int i=1;i<=mc;i++) if(d[ed][i]!=d[0][0]&&d[ed][i]+i<=d[ed][sta[top]]+sta[top]) { while(top>1&& getx(i,sta[top-1])>=getx(sta[top],sta[top-1]) )top--; if(gg(i,sta[top])>0)sta[++top]=i; } LL l=1,r,ans=0; for(int i=top;i>=2;i--) { r=gg(sta[i],sta[i-1]); LL k=sta[i],b=d[ed][sta[i]]; ans+=(r-l+1)*b+((l+r)*(r-l+1)/2)*k; l=r+1; } ans+=d[ed][0]; printf("%lld %lld\n",l,ans); } } return 0;}