话说为什么出题人老是卡$SPFA$啊$qwq$

然而$SPFA$硬是让本宝宝写成了$dij$

分情况讨论就好

/**************************************************************    Problem: 2662    User: zhangheran    Language: C++    Result: Accepted    Time:12 ms    Memory:1356 kb****************************************************************/ #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;int n,m,k;struct data{    int u;int v;int value;int next;}edge[2005];int alist[1010];int cnt;void add(int u,int v,int value){    edge[cnt].v=v;    edge[cnt].u=u;    edge[cnt].value=value;    edge[cnt].next=alist[u];    alist[u]=cnt++;    return ;}struct node{
   int u;int v;};queue
          
            q;int d[55][105];bool ins[55][105];void spfa(){ d[0][1]=0; ins[0][1]=true; q.push((node){ 0,1}); while(!q.empty()) { node x=q.front(); q.pop(); ins[x.u][x.v]=false; int next=alist[x.v]; while(next!=-1) { int v=edge[next].v; if(d[x.u][v]>d[x.u][x.v]+edge[next].value){ d[x.u][v]=d[x.u][x.v]+edge[next].value; if(!ins[x.u][v]) ins[x.u][v]=true, q.push((node{x.u,v})); } next=edge[next].next; } if(x.u
           
            d[x.u][x.v]+edge[next].value/2){ d[x.u+1][v]=d[x.u][x.v]+edge[next].value/2; if(!ins[x.u+1][v]) ins[x.u+1][v]=true, q.push((node){x.u+1,v}); } next=edge[next].next; } } }}int u,v,value;int main(){ scanf("%d%d%d",&n,&m,&k); memset(d,0x3f3f3f3f,sizeof(d)); memset(alist,-1,sizeof(alist)); for(int i=1;i<=m;i++) scanf("%d%d%d",&u,&v,&value), add(u,v,value), add(v,u,value); spfa(); int minn=0x3f3f3f3f; for(int i=0;i<=k;i++) minn=min(minn,d[i][n]); printf("%d",minn); return 0;}