k短路

感觉所谓Astar并不是单纯的Astar....

能够直接按照优先队列的出队顺序拿到前k短路真神奇......

感觉上大概可以证明,如果当前拿到了第k短路那么之前的k-1短路都已经拿到了?

AC POJ 2449

裸的第k短路.

  1 #include <cstdio>
  2 #include <fstream>
  3 #include <iostream>
  4  
  5 #include <cstdlib>
  6 #include <cstring>
  7 #include <algorithm>
  8 #include <cmath>
  9  
 10 #include <queue>
 11 #include <vector>
 12 #include <map>
 13 #include <set>
 14 #include <stack>
 15 #include <list>
 16  
 17 typedef unsigned int uint;
 18 typedef long long int ll;
 19 typedef unsigned long long int ull;
 20 typedef double db;
 21  
 22 using namespace std;
 23  
 24 inline int getint()
 25 {
 26     int res=0;
 27     char c=getchar();
 28     bool mi=false;
 29     while(c<'0' || c>'9') mi=(c=='-'),c=getchar();
 30     while('0'<=c && c<='9') res=res*10+c-'0',c=getchar();
 31     return mi ? -res : res;
 32 }
 33 inline ll getll()
 34 {
 35     ll res=0;
 36     char c=getchar();
 37     bool mi=false;
 38     while(c<'0' || c>'9') mi=(c=='-'),c=getchar();
 39     while('0'<=c && c<='9') res=res*10+c-'0',c=getchar();
 40     return mi ? -res : res;
 41 }
 42 
 43 
 44 //=============================================================================
 45 //=============================================================================
 46 //=============================================================================
 47 //=============================================================================
 48 
 49 const int INF=(1<<30)-1;
 50 
 51 struct edge
 52 {
 53     int in;
 54     int v;
 55     edge*nxt;
 56 }pool[105000];
 57 edge*et=pool;
 58 edge*eds[1050];
 59 void addedge(int i,int j,int v)
 60 { et->in=j; et->v=v; et->nxt=eds[i]; eds[i]=et++; }
 61 #define FOREACH_EDGE(i,j) for(edge*i=eds[j];i;i=i->nxt)
 62 
 63 int A[105000];
 64 int B[105000];
 65 int V[105000];
 66 
 67 int n,m;
 68 int st,ed;
 69 int k;
 70 
 71 int dist[1050];
 72 
 73 typedef pair<int,int> pl;
 74 void SPFA(int st)
 75 {
 76     priority_queue<pl,vector<pl>,greater_equal<pl> > q;
 77     for(int i=0;i<=n;i++) dist[i]=INF;
 78     dist[st]=0;
 79     q.push(pl(dist[st],st));
 80     while(!q.empty())
 81     {
 82         int x=q.top().second;
 83         int d=q.top().first;
 84         q.pop();
 85         if(dist[x]<d) continue;
 86         FOREACH_EDGE(i,x)
 87         if(dist[i->in]>dist[x]+i->v)
 88         {
 89             dist[i->in]=dist[x]+i->v;
 90             q.push(pl(dist[i->in],i->in));
 91         }
 92     }
 93 }
 94 
 95 struct value{ int x,H,s; value(int a,int b,int c):x(a),s(b),H(c){} };
 96 bool operator<(const value&a,const value&b)
 97 { return a.H>=b.H; }
 98 
 99 int ASTAR_BFS(int st,int ed)
100 {
101     if(dist[st]==INF) return -1;
102     if(st==ed) k++;
103     priority_queue<value> q;
104     q.push(value(st,0,dist[st]+0));
105     while(!q.empty())
106     {
107         int x=q.top().x;
108         int s=q.top().s;
109         q.pop();
110         
111         if(x==ed)
112         {
113             k--;
114             if(k==0) return s;
115         }
116         
117         FOREACH_EDGE(i,x)
118         q.push(value(i->in,s+i->v,dist[i->in]+s+i->v));
119     }
120     return -1;
121 }
122 
123 
124 
125 int main()
126 {
127     while(scanf("%d%d",&n,&m)>0)
128     {
129         et=pool;
130         memset(eds,0,sizeof(edge*)*(n+1));
131         
132         for(int i=0;i<m;i++)
133         {
134             A[i]=getint()-1;
135             B[i]=getint()-1;
136             V[i]=getint();
137             addedge(B[i],A[i],V[i]);
138         }
139         
140         st=getint()-1;
141         ed=getint()-1;
142         k=getint();
143         
144         SPFA(ed);
145         
146         et=pool;
147         memset(eds,0,sizeof(edge*)*(n+1));
148         for(int i=0;i<m;i++)
149         addedge(A[i],B[i],V[i]);
150         
151         printf("%d
",ASTAR_BFS(st,ed));
152     }
153     
154     return 0;
155 }

View Code

这份代码挤进并列rank10到rank17.....

改成手写堆或许会更快?......

AC BZOJ 1975

裸的前k短路枚举.

  1 #include <cstdio>
  2 #include <fstream>
  3 #include <iostream>
  4  
  5 #include <cstdlib>
  6 #include <cstring>
  7 #include <algorithm>
  8 #include <cmath>
  9  
 10 #include <queue>
 11 #include <vector>
 12 #include <map>
 13 #include <set>
 14 #include <stack>
 15 #include <list>
 16  
 17 typedef unsigned int uint;
 18 typedef long long int ll;
 19 typedef unsigned long long int ull;
 20 typedef double db;
 21  
 22 using namespace std;
 23  
 24 inline int getint()
 25 {
 26     int res=0;
 27     char c=getchar();
 28     bool mi=false;
 29     while(c<'0' || c>'9') mi=(c=='-'),c=getchar();
 30     while('0'<=c && c<='9') res=res*10+c-'0',c=getchar();
 31     return mi ? -res : res;
 32 }
 33 inline ll getll()
 34 {
 35     ll res=0;
 36     char c=getchar();
 37     bool mi=false;
 38     while(c<'0' || c>'9') mi=(c=='-'),c=getchar();
 39     while('0'<=c && c<='9') res=res*10+c-'0',c=getchar();
 40     return mi ? -res : res;
 41 }
 42 
 43 //==============================================================================
 44 //==============================================================================
 45 //==============================================================================
 46 //==============================================================================
 47 
 48 
 49 struct edge
 50 {
 51     int in;
 52     db v;
 53     edge*nxt;
 54 }pool[405000];
 55 edge*et=pool;
 56 edge*eds[2][5050];
 57 void addedge(int i,int j,db v,int k)
 58 { et->in=j; et->v=v; et->nxt=eds[k][i]; eds[k][i]=et++; }
 59 #define FOREACH_EDGE(i,x,k) for(edge*i=eds[k][x];i;i=i->nxt)
 60 
 61 int n,m;
 62 db E;
 63 
 64 int st,ed;
 65 db dist[5050];
 66 void SPFA()
 67 {
 68     for(int i=0;i<n;i++) dist[i]=1e40;
 69     typedef pair<db,int> pl;
 70     priority_queue<pl,vector<pl>,greater_equal<pl> > q;
 71     dist[ed]=0;
 72     q.push(pl(dist[ed],ed));
 73     while(!q.empty())
 74     {
 75         int x=q.top().second;
 76         db d=q.top().first;
 77         q.pop();
 78         if(dist[x]<d) continue;
 79         FOREACH_EDGE(i,x,1)
 80         if(dist[i->in]>dist[x]+i->v)
 81         {
 82             dist[i->in]=dist[x]+i->v;
 83             q.push(pl(dist[i->in],i->in));
 84         }
 85     }
 86 }
 87 
 88 int cnt=0;
 89 
 90 struct value{ db s,f; int x; value(){} value(db a,db b,int x):s(a),f(b),x(x){} };
 91 bool operator<(const value&a,const value&b)
 92 { return a.f>b.f; }
 93 
 94 value heap[2000000];
 95 int htot=0;
 96 
 97 void ASTAR_BFS()
 98 {
 99     if(dist[st]==1e40) return ;
100     heap[htot++]=st; 
101     push_heap(heap,heap+htot);
102     while(htot!=0)
103     {
104         value c=heap[0];
105         pop_heap(heap,heap+htot); htot--;
106         
107         if(c.x==ed)
108         {
109             if(c.s>E) break;
110             E-=c.s;
111             cnt++;
112             continue;
113         }
114         
115         FOREACH_EDGE(i,c.x,0)
116         {
117             heap[htot++]=value(c.s+i->v,c.s+i->v+dist[i->in],i->in); 
118             push_heap(heap,heap+htot);
119         }
120         
121     }
122 }
123 
124 
125 int main()
126 {
127     n=getint();
128     m=getint();
129     scanf("%lf
",&E);
130     for(int i=0;i<m;i++)
131     {
132         int a,b;
133         db c;
134         a=getint()-1;
135         b=getint()-1;
136         scanf("%lf",&c);
137         addedge(a,b,c,0);
138         addedge(b,a,c,1);
139     }
140     st=0;
141     ed=n-1;
142     
143     SPFA();
144     
145     ASTAR_BFS();
146     
147     printf("%d
",cnt);
148     
149     
150     return 0;
151 }

View Code

MLE了一发...听说priority_queue的空间是普通堆的两倍.......

卡空间的时候可以用stl的heap系列函数代替priority_queue =w= (妈呀我已经不会手打堆了怎么办怎么办)

具体用法可以在 http://www.cplusplus.com/reference/algorithm 找到.....

　　push_heap(L,R,cmp): 假设[L,R-1)是一个堆. 函数将调整位于R-1的元素位置,使整个数组满足堆的性质. 注意要先插入元素(并扩展右端界)然后再调用这个函数......

　　pop_heap(L,R,cmp): 假设[L,R)是一个堆. 函数将位于堆顶(位置L)的元素从堆中删除,并使[L,R-1)满足堆的性质.

　　make_heap(L,R,cmp): 把[L,R)排成一个满二叉堆.

代码里也稍许更改了多图的存图法......适用于需要构造多个图而边的参数相同的题目.