Bzoj 1598: [Usaco2008 Mar]牛跑步 dijkstra,堆,K短路,A*

1598: [Usaco2008 Mar]牛跑步

Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 427 Solved: 246
[Submit][Status][Discuss]

Description

BESSIE准备用从牛棚跑到池塘的方法来锻炼. 但是因为她懒,她只准备沿着下坡的路跑到池塘, 然后走回牛棚. BESSIE也不想跑得太远,所以她想走最短的路经. 农场上一共有M (1 <= M <= 10,000)条路, 每条路连接两个用1..N(1 <= N <= 1000)标号的地点. 更方便的是,如果X>Y,则地点X的高度大于地点Y的高度. 地点N是BESSIE的牛棚;地点1是池塘. 很快, BESSIE厌倦了一直走同一条路.所以她想走不同的路,更明确地讲,她想找出K (1 <= K <= 100)条不同的路经.为了避免过度劳累,她想使这K条路经为最短的K条路经. 请帮助BESSIE找出这K条最短路经的长度.你的程序需要读入农场的地图, 一些从X_i到Y_i 的路经和它们的长度(X_i, Y_i, D_i). 所有(X_i, Y_i, D_i)满足(1 <= Y_i < X_i; Y_i < X_i <= N, 1 <= D_i <= 1,000,000).

Input

* 第1行: 3个数: N, M, 和K

* 第 2..M+1行: 第 i+1 行包含3个数 X_i, Y_i, 和 D_i, 表示一条下坡的路.

Output

* 第1..K行: 第i行包含第i最短路经的长度,或-1如果这样的路经不存在.如果多条路经有同样的长度,请注意将这些长度逐一列出.

Sample Input

5 8 7
5 4 1
5 3 1
5 2 1
5 1 1
4 3 4
3 1 1
3 2 1
2 1 1

Sample Output

1
2
2
3
6
7
-1

HINT

输出解释:

路经分别为(5-1), (5-3-1), (5-2-1), (5-3-2-1), (5-4-3-1),

(5-4-3-2-1).

Source

Gold

题解：

dijkstra+堆优化+双关键字堆＋K短路＋A*

求K短路肯定要用A*的呀！！！

于是，上网把A*学懂了(其实并没有太懂)。。。

dijkstra中和A*中都用到堆了。。。

手写了两个堆。。。233

就不用系统堆^w^。

1A还是蛮给力的啦！！！

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 #define MAXN 1010
  4 #define MAXM 10010
  5 #define INF 1e9
  6 struct node
  7 {
  8     int begin,end,value,next;
  9 }edge1[MAXM];
 10 struct NODE
 11 {
 12     int begin,end,value,next;
 13 }edge2[MAXM];
 14 int cnt1,Head1[MAXN],cnt2,Head2[MAXN],n,K,dis[MAXN],pos[MAXN],Heap[100010],Heap1[100010],Time[MAXN],ans[110],SIZE;
 15 void addedge1(int bb,int ee,int vv)
 16 {
 17     edge1[++cnt1].begin=bb;edge1[cnt1].end=ee;edge1[cnt1].value=vv;edge1[cnt1].next=Head1[bb];Head1[bb]=cnt1;
 18 }
 19 void addedge2(int bb,int ee,int vv)
 20 {
 21     edge2[++cnt2].begin=bb;edge2[cnt2].end=ee;edge2[cnt2].value=vv;edge2[cnt2].next=Head2[bb];Head2[bb]=cnt2;
 22 }
 23 int read()
 24 {
 25     int s=0,fh=1;char ch=getchar();
 26     while(ch<'0'||ch>'9'){if(ch=='-')fh=-1;ch=getchar();}
 27     while(ch>='0'&&ch<='9'){s=s*10+(ch-'0');ch=getchar();}
 28     return s*fh;
 29 }
 30 void Push1(int k)
 31 {
 32     int now=k,root;
 33     while(now>1)
 34     {
 35         root=now/2;
 36         if(dis[Heap[root]]<=dis[Heap[now]])return;
 37         swap(Heap[root],Heap[now]);
 38         swap(pos[Heap[root]],pos[Heap[now]]);
 39         now=root;
 40     }
 41 }
 42 void Insert(int k)
 43 {
 44     Heap[++SIZE]=k;pos[k]=SIZE;Push1(SIZE);
 45 }
 46 void Pop1(int k)
 47 {
 48     int now,root=k;
 49     pos[Heap[k]]=0;Heap[k]=Heap[SIZE--];if(SIZE>0)pos[Heap[k]]=k;
 50     while(root<=SIZE/2)
 51     {
 52         now=root*2;
 53         if(now<SIZE&&dis[Heap[now+1]]<dis[Heap[now]])now++;
 54         if(dis[Heap[root]]<=dis[Heap[now]])return;
 55         swap(Heap[root],Heap[now]);
 56         swap(pos[Heap[root]],pos[Heap[now]]);
 57         root=now;
 58     }
 59 }
 60 void dijkstra(int start)
 61 {
 62     int i,u,v;
 63     for(i=1;i<=n;i++)dis[i]=INF;dis[start]=0;
 64     for(i=1;i<=n;i++)Insert(i);
 65     while(SIZE>0)
 66     {
 67         u=Heap[1];Pop1(pos[u]);
 68         for(i=Head1[u];i!=-1;i=edge1[i].next)
 69         {
 70             v=edge1[i].end;
 71             if(dis[v]>dis[u]+edge1[i].value){dis[v]=dis[u]+edge1[i].value;Push1(pos[v]);}
 72         }
 73     }
 74 }
 75 void Push2(int k,int k1)
 76 {
 77     int now,root;
 78     Heap[++SIZE]=k;Heap1[SIZE]=k1;now=SIZE;
 79     while(now>1)
 80     {
 81         root=now/2;
 82         if(Heap1[root]<=Heap1[now])return;
 83         swap(Heap[root],Heap[now]);
 84         swap(Heap1[root],Heap1[now]);
 85         now=root;
 86     }
 87 }
 88 void Pop2()
 89 {
 90     int now,root=1;
 91     Heap[1]=Heap[SIZE];Heap1[1]=Heap1[SIZE--];
 92     while(root<=SIZE/2)
 93     {
 94         now=root*2;
 95         if(now<SIZE&&Heap1[now+1]<Heap1[now])now++;
 96         if(Heap1[root]<=Heap1[now])return;
 97         swap(Heap[root],Heap[now]);
 98         swap(Heap1[root],Heap1[now]);
 99         root=now;
100     }
101 }
102 void astar(int start)
103 {
104     int u1,u2,i,v;
105     if(dis[start]==INF)return;
106     Push2(start,dis[start]);
107     while(SIZE>0)
108     {
109         u1=Heap[1];u2=Heap1[1];Pop2();
110         Time[u1]++;
111         if(u1==1){ans[Time[u1]]=u2;if(Time[u1]==K)return;}
112         if(Time[u1]<=K)
113         {
114             for(i=Head2[u1];i!=-1;i=edge2[i].next)
115             {
116                 v=edge2[i].end;
117                 Push2(v,u2-dis[u1]+dis[v]+edge2[i].value);
118             }
119         }
120     }
121 }
122 int main()
123 {
124     freopen("cowjog.in","r",stdin);
125     freopen("cowjog.out","w",stdout);
126     int m,bb,ee,vv,i;
127     n=read();m=read();K=read();
128     memset(Head1,-1,sizeof(Head1));cnt1=1;
129     memset(Head2,-1,sizeof(Head2));cnt2=1;
130     for(i=1;i<=m;i++)
131     {
132         bb=read();ee=read();vv=read();
133         addedge1(ee,bb,vv);
134         addedge2(bb,ee,vv);
135     }
136     SIZE=0;
137     dijkstra(1);
138     SIZE=0;
139     astar(n);
140     for(i=1;i<=K;i++)
141     {
142         if(ans[i]==0)printf("-1
");
143         else printf("%d
",ans[i]);
144     }
145     fclose(stdin);
146     fclose(stdout);
147     return 0;
148 }