Bzoj 1726: [Usaco2006 Nov]Roadblocks第二短路 dijkstra,堆,A*,次短路

1726: [Usaco2006 Nov]Roadblocks第二短路

Time Limit: 5 Sec  Memory Limit: 64 MB
Submit: 969  Solved: 468
[Submit][Status][Discuss]

Description

贝茜把家搬到了一个小农场，但她常常回到FJ的农场去拜访她的朋友。贝茜很喜欢路边的风景，不想那么快地结束她的旅途，于是她每次回农场，都会选择第二短的路径，而不象我们所习惯的那样，选择最短路。 贝茜所在的乡村有R(1<=R<=100,000)条双向道路，每条路都联结了所有的N(1<=N<=5000)个农场中的某两个。贝茜居住在农场1，她的朋友们居住在农场N（即贝茜每次旅行的目的地）。 贝茜选择的第二短的路径中，可以包含任何一条在最短路中出现的道路，并且，一条路可以重复走多次。当然咯，第二短路的长度必须严格大于最短路（可能有多条）的长度，但它的长度必须不大于所有除最短路外的路径的长度。

Input

* 第1行: 两个整数，N和R，用空格隔开

* 第2..R+1行: 每行包含三个用空格隔开的整数A、B和D，表示存在一条长度为 D(1 <= D <= 5000)的路连接农场A和农场B

Output

* 第1行: 输出一个整数，即从农场1到农场N的第二短路的长度

Sample Input

4 4
1 2 100
2 4 200
2 3 250
3 4 100

Sample Output

450

输出说明:

最短路：1 -> 2 -> 4 (长度为100+200=300)
第二短路：1 -> 2 -> 3 -> 4 (长度为100+250+100=450)

HINT

Source

Gold

dijkstra+堆优化+A*

这道题可以正着跑个最短路，倒着跑个最短路，然后枚举每一条边，依次替换即可。

然而我刚学习了A*，就拿A*水了水。

A*果然快的飞起。。。

 #include<bits/stdc++.h>
 using namespace std;
 #define MAXN 5010
 #define MAXM 100010
 #define INF 1e9
 struct node
 {
     int begin,end,value,next;
 }edge[*MAXM];
 int cnt,Head[MAXN],cdl,pos[MAXN],Heap[MAXN*],Heap1[MAXN*],dis[MAXN],n,SIZE,Time[MAXN];
 void addedge(int bb,int ee,int vv)
 {
     edge[++cnt].begin=bb;edge[cnt].end=ee;edge[cnt].value=vv;edge[cnt].next=Head[bb];Head[bb]=cnt;
 }
 void addedge1(int bb,int ee,int vv)
 {
     addedge(bb,ee,vv);addedge(ee,bb,vv);
 }
 int read()
 {
     int s=,fh=;char ch=getchar();
     while(ch<''||ch>''){if(ch=='-')fh=-;ch=getchar();}
     while(ch>=''&&ch<=''){s=s*+(ch-'');ch=getchar();}
     return s*fh;
 }
 void Push1(int k)
 {
     int now=k,root;
     while(now>)
     {
         root=now/;
         if(dis[Heap[root]]<=dis[Heap[now]])return;
         swap(Heap[root],Heap[now]);
         swap(pos[Heap[root]],pos[Heap[now]]);
         now=root;
     }
 }
 void Insert(int k)
 {
     Heap[++SIZE]=k;pos[k]=SIZE;Push1(SIZE);
 }
 void Pop1(int k)
 {
     int now,root=k;
     pos[Heap[k]]=;Heap[k]=Heap[SIZE--];if(SIZE>)pos[Heap[k]]=k;
     while(root<=SIZE/)
     {
         now=root*;
         if(now<SIZE&&dis[Heap[now+]]<dis[Heap[now]])now++;
         if(dis[Heap[root]]<=dis[Heap[now]])return;
         swap(Heap[root],Heap[now]);
         swap(pos[Heap[root]],pos[Heap[now]]);
         root=now;
     }
 }
 void dijkstra(int start)
 {
     int i,u,v;
     for(i=;i<=n;i++)dis[i]=INF;dis[start]=;
     for(i=;i<=n;i++)Insert(i);
     while(SIZE>)
     {
         u=Heap[];Pop1(pos[u]);
         for(i=Head[u];i!=-;i=edge[i].next)
         {
             v=edge[i].end;
             if(dis[v]>dis[u]+edge[i].value){dis[v]=dis[u]+edge[i].value;Push1(pos[v]);}
         }
     }
 }
 void Push2(int k,int k1)
 {
     int now,root;
     Heap[++SIZE]=k;Heap1[SIZE]=k1;now=SIZE;
     while(now>)
     {
         root=now/;
         if(Heap1[root]<=Heap1[now])return;
         swap(Heap[root],Heap[now]);
         swap(Heap1[root],Heap1[now]);
         now=root;
     }
 }
 void Pop2()
 {
     int now,root;
     Heap[]=Heap[SIZE];Heap1[]=Heap1[SIZE--];root=;
     while(root<=SIZE/)
     {
         now=root*;
         if(now<SIZE&&Heap1[now+]<Heap1[now])now++;
         if(Heap1[root]<=Heap1[now])return;
         swap(Heap[root],Heap[now]);
         swap(Heap1[root],Heap1[now]);
         root=now;
     }
 }
 void astar(int start)
 {
     int u1,u2,i,v;
     Push2(start,dis[start]);
     while(SIZE>)
     {
         u1=Heap[];u2=Heap1[];Pop2();
         Time[u1]++;
         if(u1==n&&Time[u1]==){cdl=u2;return;}
         if(Time[u1]>)continue;
         for(i=Head[u1];i!=-;i=edge[i].next)
         {
             v=edge[i].end;
             Push2(v,u2-dis[u1]+dis[v]+edge[i].value);
         }
     }
 }
 int main()
 {
     freopen("block.in","r",stdin);
     freopen("block.out","w",stdout);
     int bb,ee,vv,m,i;
     n=read();m=read();
     memset(Head,-,sizeof(Head));cnt=;
     for(i=;i<=m;i++)
     {
         bb=read();ee=read();vv=read();
         addedge1(ee,bb,vv);
     }
     dijkstra(n);
     cdl=;SIZE=;
     astar();
     printf("%d",cdl);
     fclose(stdin);
     fclose(stdout);
     return ;
 }