映射二叉堆+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;
}
补充:移动开发 , Android ,