K短路 spfa + A*

  1 #include <stdio.h>
  2 #include <string.h>
  3 #include <queue>
  4 #include <algorithm>
  5 using namespace std;
  6 const int L = 100005;
  7 const int inf = 1<<30;
  8 struct node
  9 {
 10     int now,g,f;
 11     bool operator <(const node a)const
 12     {
 13         if(a.f == f) return a.g < g;
 14         return a.f < f;
 15     }
 16 };
 17 struct edges
 18 {
 19     int x,y,w,next;
 20 } e[L<<2],re[L<<2];//e是输入给出的定向图，re为其逆向图，用于求t到其他所有点的最短路径
 21 
 22 int head[1005],dis[1005],vis[1005],n,m,k,s,t,rehead[1005];
 23 
 24 void Init()//初始化
 25 {
 26     memset(e,-1,sizeof(e));
 27     memset(re,-1,sizeof(re));
 28     for(int i = 0; i<=n; i++)
 29     {
 30         dis[i] = inf;
 31         vis[i] = 0;
 32         head[i] = -1;
 33         rehead[i] = -1;
 34     }
 35 }
 36 
 37 void AddEdges(int x,int y,int w,int k)
 38 {
 39     e[k].x = x,e[k].y = y,e[k].w = w,e[k].next = head[x],head[x] = k;
 40     re[k].x = y,re[k].y = x,re[k].w = w,re[k].next = rehead[y],rehead[y] = k;
 41 }
 42 
 43 int relax(int u,int v,int c)
 44 {
 45     if(dis[v]>dis[u]+c)
 46     {
 47         dis[v] = dis[u]+c;
 48         return 1;
 49     }
 50     return 0;
 51 }
 52 
 53 void SPFA(int src)
 54 {
 55     int i;
 56     dis[src] = 0;
 57     queue<int> Q;
 58     Q.push(src);
 59     while(!Q.empty())
 60     {
 61         int u,v;
 62         u = Q.front();
 63         Q.pop();
 64         vis[u] = 0;
 65         for(i = rehead[u]; i!=-1; i = re[i].next)
 66         {
 67             v = re[i].y;
 68             if(relax(u,v,re[i].w) && !vis[v])
 69             {
 70                 Q.push(v);
 71                 vis[v] = 1;
 72             }
 73         }
 74     }
 75 }
 76 
 77 int Astar(int src,int to)
 78 {
 79     priority_queue<node> Q;
 80     int i,cnt = 0;
 81     if(src == to) k++;//在起点与终点是同一点的情况下，k要+1
 82     if(dis[src] == inf) return -1;
 83     node a,next;
 84     a.now = src;
 85     a.g = 0;
 86     a.f = dis[src];
 87     Q.push(a);
 88     while(!Q.empty())
 89     {
 90         a = Q.top();
 91         Q.pop();
 92         if(a.now == to)
 93         {
 94             cnt++;
 95             if(cnt == k)
 96                 return a.g;
 97         }
 98         for(i = head[a.now]; i!=-1; i = e[i].next)
 99         {
100             next = a;
101             next.now = e[i].y;
102             next.g = a.g+e[i].w;
103             next.f = next.g+dis[next.now];
104             Q.push(next);
105 
106         }
107     }
108     return -1;
109 }
110 
111 int main()
112 {
113     int i,j,x,y,w;
114     while(~scanf("%d%d",&n,&m))
115     {
116         Init();
117         for(i = 0; i<m; i++)
118         {
119             scanf("%d%d%d",&x,&y,&w);
120             AddEdges(x,y,w,i);
121         }
122         scanf("%d%d%d",&s,&t,&k);
123         SPFA(t);
124         printf("%d
",Astar(s,t));
125     }
126 
127     return 0;
128 }
View Code