用到A*

推两篇博客

板子

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              using namespace std;const int INF=0x3f3f3f3f;typedef pair
              
                pr;typedef long long ll;#define fi first#define se second#define me(x) memset(x, -1, sizeof(x))#define mem(x) memset(x, 0, sizeof(x))#define N 20000+5#define NIL -1struct edg{ int next, to, w;}edge[N], edge1[N];struct node{ int p, h, g; bool operator<(node x) const { return x.g+x.h
               
                 s;void init(){ s.clear(); cnt=0; cnt1=0; me(head); mem(vis); me(head1); mem(t); for(int i=1; i<=n; i++) dist[i]=INF;}void add(int u, int v, int w){ edge[cnt].w=w; edge[cnt].to=v; edge[cnt].next=head[u]; head[u]=cnt++;}void add1(int u, int v, int w){ edge1[cnt1].w=w; edge1[cnt1].to=v; edge1[cnt1].next=head1[u]; head1[u]=cnt1++;}void dijkstra(int z){ s.insert(z); dist[z]=0; while(s.size()) { int v=*s.begin(); s.erase(v); vis[v]=1; for(int i=head1[v]; ~i; i=edge1[i].next) { int t=edge1[i].to; if(!vis[t] && dist[t]>dist[v]+edge1[i].w) { s.erase(t); dist[t]=dist[v]+edge1[i].w; s.insert(t); } } }}priority_queue
                
                  que;int astar(int s, int e){ node x, y; x.g=0; x.h=0; x.p=s; que.push(x); while(que.size()) { x=que.top(); que.pop(); t[x.p]++; if(t[x.p]==k && x.p==e) return x.h+x.g; if(t[x.p]>k) continue; for(int i=head[x.p]; ~i; i=edge[i].next) { y.p=edge[i].to; y.g=dist[edge[i].to]; y.h=edge[i].w+x.h; que.push(y); } } return -1;}int main(){ int i, j, z; int x, y, u, v, w; while(cin>>n>>m) { init(); for(i=0; i
                 
                  >u>>v>>w, add(u, v, w), add1(v, u, w); cin>>x>>y>>k; dijkstra(y); z=astar(x, y); cout<
                  
                   <