dijkstra邻接表list怎么建(用C++,不要用类写)

来源:百度知道 编辑:UC知道 时间:2024/05/28 19:20:39

//这是我自己写的模版你拿去吧
#include <deque>
#include <queue>
#include <iostream>
using namespace std;
#define INF (1<<29)
#define MN 5005
int n,m;//点最大标号不超过n[0..n]
struct e
{
int v,w;
int next;
}E[MN*MN*2];
int head[MN];
int fe;
void init(int n)
{
fe=0;
int i;
for(i=0;i<=n;++i)head[i]=-1;
}
void add_edg(int s,int t,int w)//有向图,在加入边前必须init(n);
{
E[fe].v=t;
E[fe].w=w;
E[fe].next=head[s];
head[s]=fe++;
}
struct node
{
int v;
int cdis;
node(int vv,int dd){v=vv;cdis=dd;}
node(){}

};
bool operator < (const node aa,const node bb)
{
return aa.dis>bb.dis;//最小堆
}
int dis[MN];
void dijkstra(int s)//s是源点
{
node tmp;
int i,k,v,w;
for(i=1;i<=n;++i){dis[i]=INF;}
priority_queue < node,deque<node> > Q;
Q.push(n