n<=1000而m<=10000的DAG中求从n到1的前K<=100短路，不存在输出-1。

方法一：之前写过“第二短路”，比较2次；如果是要“前K短路”的话，dis需要是一个支持查找、插入（找到一个新的第u大，u<=K，需要插入u）、删除（插入后把最后一个删除）的东西，那就Treap或者Splay乱写一通啦。代码如下：

如下个头。编程复杂度不说，一定要用SPFA实现，正确性不明，时间复杂度也难说。

方法二：查了题解。根据数据规模和图的特点选择A*：数据n和K都较小，可以感觉，从起点n到其它点的路程中，第v，v>=K+1短路是没有意义的；图没有环。

所以A*中，估价函数h=当前状态的运动路程+从这个点到终点的最短路。为了得到后者，需把所有的边反过来找1到每个点的最短路。

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
            6 //#include
           
             7 using namespace std; 8 9 int n,m,K; 10 #define maxn 1011 11 #define maxm 10011 12 struct Edge{ int to,v,next;}; 13 const int inf=0x7fffffff; 14 struct Graph 15 { 16 Edge edge[maxm*2];int le; 17 int first[maxn],dis[maxn],vis[maxn]; 18 struct Node 19 { 20 int x,v; 21 bool operator < (const Node &b) const { return v
            
              (const Node &b) const { return v>b.v;} 23 }; 24 priority_queue
             
              
               ,greater
               
                 > q; 25 Graph() 26 { 27 memset(first,0,sizeof(first)); 28 le=2; 29 } 30 void insert(int x,int y,int v) 31 { 32 Edge &e=edge[le]; 33 e.to=y;e.v=v; 34 e.next=first[x]; 35 first[x]=le++; 36 } 37 void Dijkstra() 38 { 39 for (int i=1;i<=n;i++) dis[i]=inf; 40 memset(vis,0,sizeof(vis)); 41 dis[1]=0; 42 q.push((Node){ 1,0}); 43 while (!q.empty()) 44 { 45 const int now=q.top().x,d=q.top().v; 46 q.pop(); 47 if (vis[now]) continue; 48 vis[now]=1; 49 for (int i=first[now];i;i=edge[i].next) 50 if (dis[edge[i].to]>d+edge[i].v) 51 { 52 dis[edge[i].to]=d+edge[i].v; 53 q.push((Node){edge[i].to,dis[edge[i].to]}); 54 } 55 } 56 } 57 }reG,G; 58 struct heapnode 59 { 60 int x,f,g; 61 bool operator < (const heapnode &b) const 62 { return f+g
                
                  (const heapnode &b) const 64 { return f+g>b.f+b.g;} 65 }; 66 priority_queue
                 
                  
                   ,greater
                   
                     > que; 67 int ans[maxn],cnt[maxn]; 68 void Astar() 69 { 70 que.push((heapnode){n,0,reG.dis[n]}); 71 cnt[n]=1; 72 while (!que.empty()) 73 { 74 const int x=que.top().x,d=que.top().f; 75 que.pop(); 76 if (cnt[x]==K) continue; 77 cnt[x]++; 78 if (x==1) 79 { 80 ans[cnt[x]]=d; 81 if (cnt[x]==K) break; 82 } 83 for (int i=G.first[x];i;i=G.edge[i].next) 84 que.push((heapnode){G.edge[i].to,G.edge[i].v+d,reG.dis[G.edge[i].to]}); 85 } 86 } 87