POJ 3255 - 求两点间的第二短路

注意这里求的不是两点间的第二短长度...就是说如果两点间距离有两条路径都是最短路径~~那最第二短路径长度还是这个最短路径..

做了POJ2449的两点间K短路后这道题就是它的缩小版...唯一要留意的就是边是无向边....

Program:

#include<iostream>
#include<queue>
#define MAXN 200001
using namespace std;
struct node
{
     int h,g,p;
     bool operator < (node a) const
     {
          return a.h+a.g<h+g;     
     }     
};
struct nodeOfLine
{
     int x,y,w,next;      
}line[MAXN];
int n,r,link[5001],g[5001];
priority_queue<node> myqueue;
void djikstra()
{
    int i,j,k,t;  
    bool used[MAXN];
    memset(g,0x7F,sizeof(g)); 
    memset(used,false,sizeof(used));
    g[n]=0;
    for (t=1;t<=n;t++)
    {
         j=0;
         for (i=1;i<=n;i++)
           if (!used[i] && (!j || g[i]<g[j])) j=i; 
         used[j]=true;
         k=link[j];
         while (k)
         {
              if (g[line[k].y]>g[line[k].x]+line[k].w)  
                   g[line[k].y]=g[line[k].x]+line[k].w; 
              k=line[k].next;      
         }
    }
    return;
}
int Astar()
{
    node h,temp;
    int times[5001],k;
    while (!myqueue.empty()) myqueue.pop();
    memset(times,0,sizeof(times)); 
    h.p=1; h.h=h.g=0; 
    myqueue.push(h);
    while (!myqueue.empty())
    {
          h=myqueue.top();
          myqueue.pop();
          times[h.p]++;
          if (times[h.p]>2) continue;
          if (times[h.p]==2 && h.p==n) return h.h+h.g;
          k=link[h.p];
          while (k)
          {
                temp.p=line[k].y;
                temp.h=h.h+line[k].w;
                temp.g=g[line[k].y];
                myqueue.push(temp);
                k=line[k].next;     
          }         
    }
    return -1;
}
int main()
{ 
    scanf("%d%d",&n,&r);
    memset(link,0,sizeof(link)); 
    for (int i=1;i<=r;i++)
    {          
          scanf("%d%d%d",&line[i*2-1].x,&line[i*2-1].y,&line[i*2-1].w);
          line[i*2-1].next=link[line[i*2-1].x]; link[line[i*2-1].x]=i*2-1;
          line[i*2].x=line[i*2-1].y; line[i*2].y=line[i*2-1].x; line[i*2].w=line[i*2-1].w;
          line[i*2].next=link[line[i*2].x]; link[line[i*2].x]=i*2;
    } 
    r*=2;
    djikstra();
    printf("%d\n",Astar());
    return 0;   
}