k短路(A*)

http://poj.org/problem?id=2449

  1 #include <cstdio>
  2 #include <cstdlib>
  3 #include <cstring>
  4 #include <queue>
  5 #include <algorithm>
  6 using namespace std;
  7 const int maxn=1e3+10;
  8 
  9 /**
 10 求第K短的算法基于BFS搜索，当终点出队K次时，所走的总距离就是第K短路，
 11 不过这样那些不该走的路会被反复的走，造成许多空间时间浪费，这时候就要用到启发式的A*搜索
 12 **/
 13 
 14 ///from s to t
 15 ///opp:from t to s
 16 
 17 struct node
 18 {
 19     int d,len;
 20     node *next;
 21 }*e[maxn],*oppe[maxn];
 22 
 23 ///h:from this point to destination(predict must:predict<actual)
 24 ///g:from source to this point(actual)
 25 int h[maxn],unreach;
 26 
 27 struct rec
 28 {
 29     int d,dist;
 30     bool operator<(const rec &b) const
 31     {
 32         return b.dist<dist;
 33     }
 34 };
 35 priority_queue<rec>st;
 36 
 37 struct noa
 38 {
 39     int d,dist,pre;
 40     bool operator<(const noa &b) const
 41     {
 42         if (b.pre==pre)
 43             return b.dist<dist;
 44         return b.pre<pre;
 45     }
 46 };
 47 priority_queue<noa>ast;
 48 
 49 bool vis[maxn];
 50 int s,t,ind,ci[maxn];
 51 
 52 int astar()
 53 {
 54     int d,dist;
 55     node *p;
 56     ///多组数据时需要
 57 //    while (!ast.empty())
 58 //        ast.pop();
 59     if (h[s]!=unreach)
 60         ast.push({s,0,h[s]});
 61     while (!ast.empty())
 62     {
 63         d=ast.top().d;
 64         dist=ast.top().dist;
 65         ast.pop();///!
 66         ci[d]++;
 67         if (ci[d]==ind && d==t)
 68             return dist;///而不是ast.top().dist
 69         ///优化
 70         if (ci[d]>ind)
 71             continue;
 72 
 73         p=e[d];
 74         while (p)
 75         {
 76             if (h[p->d]!=unreach)
 77                 ///aster
 78                 ast.push({p->d,dist+p->len,dist+p->len+h[p->d]});
 79                 ///just dijkstra
 80 //                ast.push({p->d,dist+p->len,dist+p->len});
 81             p=p->next;
 82         }
 83     }
 84     return -1;
 85 }
 86 
 87 void opp_dijkstra()
 88 {
 89     int d,dd;
 90     node *p;
 91     memset(h,0x7f,sizeof(h));
 92     unreach=h[0];
 93     h[t]=0;
 94     st.push({t,0});
 95     while (1)
 96     {
 97         while (!st.empty() && vis[st.top().d])
 98             st.pop();
 99         if (st.empty())
100             break;
101          d=st.top().d;
102          st.pop();
103          vis[d]=1;
104          p=oppe[d];///
105          while (p)
106          {
107              dd=p->d;
108              if (h[dd]>h[d]+p->len)
109              {
110                  h[dd]=h[d]+p->len;
111                  st.push({dd,h[dd]});
112              }
113              p=p->next;
114          }
115     }
116 }
117 
118 int main()
119 {
120     int a,b,c,n,m,i;
121     node *p;
122     scanf("%d%d",&n,&m);
123     for (i=1;i<=m;i++)
124     {
125         scanf("%d%d%d",&a,&b,&c);
126         p=new node();
127         p->d=b;
128         p->len=c;
129         p->next=e[a];
130         e[a]=p;
131 
132         p=new node();
133         p->d=a;
134         p->len=c;
135         p->next=oppe[b];
136         oppe[b]=p;
137     }
138     scanf("%d%d%d",&s,&t,&ind);
139     ///!!!
140     if (s==t)
141         ind++;
142 //        ///shortest path
143 //        scanf("%d%d",&s,&t);
144 //        ind=1;
145     opp_dijkstra();
146     printf("%d",astar());
147     return 0;
148 }
149 /*
150 2 2
151 1 2 1
152 2 1 1
153 1 1 1
154 
155 3 3
156 1 2 1
157 2 3 2
158 3 2 1
159 1 1 1
160 
161 3 3
162 1 2 1
163 2 3 2
164 3 1 3
165 1 1 2
166 
167 3 1
168 1 2 3
169 1 3 1
170 
171 3 2
172 1 2 10
173 2 3 2
174 1 3 1
175 
176 3 2
177 1 2 10
178 2 3 2
179 1 3 2
180 
181 4 4
182 1 3 2
183 3 2 5
184 1 4 3
185 4 2 1
186 1 2 2
187 
188 x
189 4 4
190 1 2 100000
191 2 3 1
192 3 2 1
193 3 4 100000
194 1 4 1000
195 
196 3 4
197 1 2 1
198 2 1 2
199 2 3 1
200 3 2 1
201 2 3 5
202 
203 3 3
204 1 2 1000
205 1 3 1
206 3 2 1
207 1 2 1
208 
209 */

https://www.luogu.org/problemnew/show/P2483

68分……

  1 #include <cstdio>
  2 #include <cstdlib>
  3 #include <cstring>
  4 #include <queue>
  5 #include <algorithm>
  6 using namespace std;
  7 const int maxn=5e3+10;
  8 
  9 struct node
 10 {
 11     int d;
 12     double len;
 13     node *next;
 14 }*e[maxn],*oppe[maxn];
 15 
 16 ///h:from this point to destination(predict must:predict<actual)
 17 ///g:from source to this point(actual)
 18 double h[maxn],unreach;
 19 double tot;
 20 
 21 struct rec
 22 {
 23     int d;
 24     double dist;
 25     bool operator<(const rec &b) const
 26     {
 27         return b.dist<dist;
 28     }
 29 };
 30 priority_queue<rec>st;
 31 
 32 struct noa
 33 {
 34     int d,g;
 35     double dist,pre;
 36     bool operator<(const noa &b) const
 37     {
 38         if (b.pre==pre)
 39             return b.dist<dist;
 40         return b.pre<pre;
 41     }
 42 };
 43 priority_queue<noa>ast;
 44 
 45 bool vis[maxn];
 46 int s,t,ind,re,n,m;
 47 int ci[maxn];
 48 
 49 void aster()
 50 {
 51     int d,dd,g;
 52     double dist,ddist;
 53     node *p;
 54     ind=tot/h[1];///限制次数
 55 
 56     if (h[s]!=unreach)
 57         ast.push({s,0,0,h[s]});
 58     while (!ast.empty())
 59     {
 60         d=ast.top().d;
 61         dist=ast.top().dist;
 62         g=ast.top().g;
 63         ast.pop();///!
 64         ci[d]++;
 65         if (d==t)
 66         {
 67             if (dist>tot)
 68                 return;
 69             tot-=dist;
 70             re++;
 71             ind=re+tot/dist;///限制次数，优化
 72             continue;   ///这题的坑爹地方：到达终点，就不能再走了
 73         }
 74 
 75         p=e[d];
 76         while (p)
 77         {
 78             dd=p->d;
 79             ddist=dist+p->len;
 80             if (h[dd]!=unreach && g!=m && ci[dd]<ind && ddist<=tot)
 81                 ast.push({dd,g+1,ddist,ddist+h[p->d]});
 82             p=p->next;
 83         }
 84     }
 85 }
 86 
 87 void opp_dijkstra()
 88 {
 89     int d,dd,i;
 90     node *p;
 91     unreach=1.0e11;
 92     for (i=1;i<=n;i++)
 93         h[i]=unreach;
 94 
 95     h[t]=0;
 96     st.push({t,0});
 97     while (1)
 98     {
 99         while (!st.empty() && vis[st.top().d])
100             st.pop();
101         if (st.empty())
102             break;
103          d=st.top().d;
104          st.pop();
105          vis[d]=1;
106          p=oppe[d];///
107          while (p)
108          {
109              dd=p->d;
110              if (h[dd]>h[d]+p->len)
111              {
112                  h[dd]=h[d]+p->len;
113                  st.push({dd,h[dd]});
114              }
115              p=p->next;
116          }
117     }
118 }
119 
120 int main()
121 {
122     int a,b,i;
123     double c;
124     node *p,*pp;
125     scanf("%d%d",&n,&m);
126     scanf("%lf",&tot);
127     for (i=1;i<=m;i++)
128     {
129         scanf("%d%d%lf",&a,&b,&c);
130         p=new node();
131         p->d=b;
132         p->len=c;
133         p->next=e[a];
134         e[a]=p;
135 
136         p=new node();
137         p->d=a;
138         p->len=c;
139         p->next=oppe[b];
140         oppe[b]=p;
141     }
142     s=1,t=n;
143     opp_dijkstra();
144     ///lower the memory
145     for (i=1;i<=n;i++)
146     {
147         p=oppe[i];
148         while (p)
149         {
150             pp=p;
151             p=p->next;
152             free(pp);
153         }
154     }
155     aster();
156     printf("%d",re);
157     return 0;
158 }