一开始傻逼地想用floyd。。。然后正解Dp，难得地一次A了。。。

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             typedef long long LL;using namespace std;const int maxn=200;const int maxm=50;int n,m,kk,e,d,x,y,z,fir[maxm],nxt[maxm*maxm],to[maxm*maxm],val[maxm*maxm],ecnt,no[maxn][maxm];int dis[maxm],vis[maxm],dp[maxn][maxn],f[maxn];bool ok[maxm];void add(int u,int v,int w) { nxt[++ecnt]=fir[u]; fir[u]=ecnt; to[ecnt]=v; val[ecnt]=w; nxt[++ecnt]=fir[v]; fir[v]=ecnt; to[ecnt]=u; val[ecnt]=w;}queue
             
              q;int spfa(int l,int r) { memset(dis,127,sizeof(dis)); memset(vis,0,sizeof(dis)); memset(ok,0,sizeof(ok)); for(int i=l;i<=r;i++) { for(int j=1;j<=no[i][0];j++) ok[no[i][j]]=1; } vis[1]=1; dis[1]=0; q.push(1); while(!q.empty()) { int now=q.front(); q.pop(); vis[now]=0; for(int i=fir[now];i;i=nxt[i]) if(!ok[to[i]]){ if(dis[to[i]]>dis[now]+val[i]) { dis[to[i]]=dis[now]+val[i]; if(!vis[to[i]]) { vis[to[i]]=1; q.push(to[i]); } } } } return dis[m];}int main(){ //freopen(".in","r",stdin); //freopen(".out","w",stdout); scanf("%d%d%d%d",&n,&m,&kk,&e); for(int i=1;i<=e;i++) { scanf("%d%d%d",&x,&y,&z); add(x,y,z); } scanf("%d",&d); for(int i=1;i<=d;i++) { scanf("%d%d%d",&x,&y,&z); for(int j=y;j<=z;j++) { no[j][++no[j][0]]=x; } } for(int i=1;i<=n;i++) for(int j=i;j<=n;j++) dp[i][j]=spfa(i,j); for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]+1); } memset(f,127/3,sizeof(f)); f[0]=0; for(int i=1;i<=n;i++) for(int j=0;j
              
               0)); } printf("%d\n",f[n]); return 0;}