题目

 

 

分析

k短路，Astar。估价函数是终点向外跑的最短路。

显然不是正解qwq。

 

代码

// By noble_// Astar algorithm// #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            using namespace std;const int maxn = 10050;double h[maxn];int n,m,s,t;struct Edge{ int u,v; double dis; };struct Node{ int x;double dis,g; bool operator < (const Node& a) const{ return dis>a.dis; }// Node(int xx,double d){x=xx;dis=d;}};priority_queue
            
              que;struct QwQ{ vector
             
               edges; vector
              
                G[maxn]; int vis[maxn]; //传边反着穿 void Addedge(int u,int v,double dis) { edges.push_back((Edge){u,v,dis}); G[u].push_back(edges.size()-1); } void dijkstra() { while(!que.empty()) que.pop(); memset(vis,0,sizeof(vis)); for(int i=0;i<=n;i++) h[i]=1e8; que.push((Node){t,0,0}); h[t]=0; while(!que.empty()) { Node x=que.top(); que.pop(); if(vis[x.x]) continue; // printf("======== %d %f\n",x.x,x.dis); vis[x.x]=1; for(int i=0;i
               
                = h[x.x] + e.dis) { // printf("===== %d -> %d\n",x.x,e.v); h[e.v] = h[x.x] + e.dis; que.push((Node){e.v,h[e.v],0}); } } } // printf("--- %d %d\n",(int)h[1],(int)h[2]); }}qwq;vector
                
                  edges;vector
                 
                   G[maxn];int reach[maxn], k, ans=0;double p, sum=0;void Addedge(int u,int v,double dis) { edges.push_back((Edge){u,v,dis}); G[u].push_back(edges.size()-1);}void Astar() { while(!que.empty()) que.pop();// if(h[s] >= 1e8) return -1; memset(reach,0,sizeof(reach));// priority_queue
                  
                    que; que.push((Node){s,h[s],0}); while(!que.empty()) { Node x=que.top(); que.pop(); // printf("---- %d %f\n",x.x,x.dis); reach[x.x]++; if(reach[x.x]>k)continue; if(x.x==t) { if(sum+x.g <= p) sum+=x.g,ans++; else break; } for(int i=0;i