poj 3377(bfs+priority

poj 3377(bfs+priority_queue)

题意：

有个城市被一条河分成了南北两部分, 它们之间有N+1个航道, 标记为0~N, 每个航道的两端是一个码头, 然后每个码头都只属于一个航道, 航道间也不交叉. 现在给出各航道的航行时间以及同一河岸上各码头间的行走时间, 求出从起点S出发到终点T所需的最短时间.

分析：

一共有6种点:
①点在北岸且不是左右端点, 则它可以往左, 右走, 或通过航道去南岸;
②点在南岸且不是左右端点, 则它可以往左, 右走, 或通过航道去北岸;
③点是北岸左端点, 则它可以往右走, 或通过航道去南岸;
④点是北岸右端点, 则它可以往左走, 或通过航道去南岸;
⑤点是南岸左端点, 则它可以往右走, 或通过航道去北岸;
⑥点是南岸右端点, 则它可以往左走, 或通过航道去北岸;

利用优先队列从起始点按照以上六种点开始拓展。

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <queue>
  4 #include <cstring>
  5 
  6 using namespace std;
  7 
  8 #define MAXN 1000010
  9 
 10 struct dist
 11 {
 12     int id;
 13     __int64 val;
 14     bool operator <(const dist & a) const 
 15     {
 16         return val>a.val;
 17     }
 18 }next,tmp;
 19 
 20 priority_queue<dist> Q;
 21 __int64 dis[2*MAXN],ferry[MAXN];
 22 bool vis[MAXN*2];
 23 int N;
 24 int st,end;
 25 
 26 void relax(int k,__int64 dis)
 27 {
 28     next.id=k;
 29     next.val=tmp.val+dis;
 30     Q.push(next);
 31 }
 32 
 33 __int64 bfs()
 34 {
 35     for(int i=0;i<2*MAXN;i++)
 36         vis[i]=0;
 37     while(!Q.empty())
 38         Q.pop();
 39     tmp.id=st;
 40     tmp.val=0;
 41     Q.push(tmp);
 42     while(!Q.empty())
 43     {
 44         tmp=Q.top();
 45         Q.pop();
 46            if(tmp.id==end)
 47             return tmp.val;    
 48         if(vis[tmp.id])
 49             continue;
 50         vis[tmp.id]=1;
 51         if(tmp.id==0)
 52         {
 53             relax(N+1,ferry[0]);
 54             relax(1,dis[1]);
 55         }
 56         else if(tmp.id==N+1)
 57         {
 58             relax(0,ferry[0]);
 59             relax(tmp.id+1,dis[tmp.id+1]);
 60         }
 61         else if(tmp.id==N)
 62         {
 63             relax(tmp.id-1,dis[tmp.id]);
 64             relax(tmp.id+N+1,ferry[N]);
 65         }
 66         else if(tmp.id==2*N+1)
 67         {
 68             relax(N,ferry[N]);
 69             relax(tmp.id-1,dis[tmp.id]);
 70         }
 71         else if(tmp.id>0 && tmp.id <N)
 72         {
 73             relax(tmp.id-1,dis[tmp.id]);
 74             relax(tmp.id+1,dis[tmp.id+1]);
 75             relax(tmp.id+N+1,ferry[tmp.id]);
 76         }
 77         else if(tmp.id>N+1 && tmp.id<2*N+1)
 78         {
 79             relax(tmp.id-1,dis[tmp.id]);
 80             relax(tmp.id+1,dis[tmp.id+1]);
 81             relax(tmp.id-N-1,ferry[tmp.id-N-1]);
 82         }
 83     }
 84     return -1;
 85 }
 86 
 87 int main()
 88 {
 89     int x,y;
 90     while(scanf("%d",&N) &&N)
 91     {
 92         scanf("%d%d",&x,&y);
 93         st=y+x*(N+1);
 94         scanf("%d%d",&x,&y);
 95         end=y+x*(N+1);
 96         for(int i=1;i<=N;i++)
 97             scanf("%I64d",&dis[i]);
 98         for(int i=0;i<=N;i++)
 99             scanf("%I64dd",&ferry[i]);
100         for(int i=1;i<=N;i++)
101             scanf("%I64d",&dis[i+N+1]);
102         printf("%I64d\n",bfs());
103     }
104     return 0;
105 }