映射二叉堆+Dijkstra

幽幽子

[html]
#include <cstdio> 
#include <cstring> 
#define N 100010 
#define M 400010 
#define INF 999999999 
int n,m,s,a,b; 
int head[N],cnt; 
struct Edge 
{ 
    int v,next,w; 
}edge[M]; 
struct Heap 
{ 
    int d,v,p; 
}heap[N]; 
int hl,pos[N]; 
void addedge(int u,int v,int w) 
{ 
    edge[cnt].next=head[u]; edge[cnt].v=v; edge[cnt].w=w; 
    head[u]=cnt++; 
} 
void swap(int a,int b) 
{ 
    heap[0]=heap[a];    heap[a]=heap[b];    heap[b]=heap[0]; 
    pos[heap[a].v]=a;    pos[heap[b].v]=b; 
} 
void heapfy() 
{ 
    int i=2; 
    while (i<=hl) 
    { 
        if(i+1<=hl && heap[i+1].d<heap[i].d)i++; 
        if(heap[i].d<heap[i>>1].d) 
        { 
            swap(i,i>>1); 
            i<<=1;; 
        } 
        else break; 
    } 
} 
void decrease(int i) 
{ 
    while (i!=1 && heap[i].d<heap[i>>1].d) 
    { 
        swap(i,i>>1); i>>=1; 
    } 
} 
void relax(int u,int v,int w) 
{ 
    if(heap[pos[u]].d+w<heap[pos[v]].d) 
    { 
        heap[pos[v]].d=heap[pos[u]].d+w; 
        decrease(pos[v]); 
    } 
} 
void dijkstra(int s,int n) 
{ 
    int u,i; 
    for(i=1;i<=n;i++) 
    { 
        heap[i].v=pos[i]=i;    heap[i].d=INF; 
    } 
    heap[s].p=s;    heap[s].d=0;    swap(1,s);    hl=n; 
    while (hl) 
    { 
        u=heap[1].v; 
        swap(1,hl); 
        hl--; 
        heapfy(); 
        for(i=head[u];i!=-1;i=edge[i].next) 
            if(pos[edge[i].v]<=hl) relax(u,edge[i].v,edge[i].w); 
    } 
} 
int main () 
{ 
    int ds1,ds2,dab; 
    while (scanf("%d%d%d%d%d",&m,&n,&s,&a,&b)!=-1) 
    { 
        cnt=0; 
        memset(head,-1,sizeof(head)); 
        while (m--) 
        { 
            int u,v,w; 
            scanf("%d%d%d",&u,&v,&w); 
            addedge(u,v,w); 
            addedge(v,u,w); 
        } 
        dijkstra(s,n); 
        ds1=heap[pos[a]].d; 
        ds2=heap[pos[b]].d; 
        dijkstra(a,n); 
        dab=heap[pos[b]].d; 
        printf("%d\n",dab+(ds1<ds2?ds1:ds2)); 
    } 
     
    return 0; 
}