链式前向星模板+dijkstra堆优化模板

链式前向星模板题+dijkstra堆优化

一.链式前向星

1.链式前向星的复杂度

链式前向星的构造类似于静态建立邻接表，其复杂度只与边数e有关 – 时间复杂度：O（e），空间复杂度：O（e）。

2.链式前向星的变量

struct edge{
	int to, dis, next;
};
//to : 起点的编号		dis : 起点到终点的距离		next : 起点相同的上一条边的编号

edge e[maxn];
//记录边的信息

int head[maxn],dis[maxn],cnt;
//head[i] : 表示以i为起点的最后一条边的存储位置
//dis[i] : 第i个点的所需距离（例如最短距离等）
//cnt自加，代表边数

3.链式前向星的加边

void add(int u,int v,int d)
{
	e[++cnt].dis = d;
	e[cnt].to = v;
	e[cnt].next = head[u];
	head[u] = cnt;
}

下面的pre是为了观察比较写的，代表起点，在代码中不存在； 例如输入有4个点，4条边： ①1 2 7

②1 3 5

③1 4 5

④2 3 9

4.链式前向星的模板题

#include <bits/stdc++.h>

using namespace std;

const int maxn = 4e7 + 10;

int n,m,flag;

struct edge{
	int to,dis,next;
}e[maxn];
int head[maxn],dis[maxn],cnt;

inline void add(int u,int v,int d)
{
	e[++cnt].dis = d;
	e[cnt].to = v;
	e[cnt].next = head[u];
	head[u] = cnt;
}

int main()
{
	scanf("%d%d%d",&n,&m,&flag);
	int u,v,d;
	if(flag){
		for(int i = 1; i <= m; i++)
		{
			scanf("%d%d%d",&u,&v,&d);
			add(u,v,d);
		}
	}
	else{
		for(int i = 1; i <= m; i++)
		{
			scanf("%d%d%d",&u,&v,&d);
			add(u,v,d);
			add(v,u,d);
		}
	}
	//链式前向星的遍历
	for(int i = 1; i <= n; i++)
	{
		int k = 0;
		//例如上面的例子，从起点出发的最后一条边开始遍历，直到为0，也就是没有边了，就结束遍历
		for(int j = head[i]; j ; j = e[j].next)
		{
			printf("%d %d %d
",i,e[j].to,e[j].dis);
			k = 1;
		}
		if(!k)	printf("
");
	}
	return 0;
}

二.dijkstra + 堆优化

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 1e5 + 10;
const int minn = 0xc0c0c0c0;
const int INF = 0x3f3f3f3f;

struct edge{
	int to,dis,next;
};

edge e[500010];
int head[maxn],dis[maxn],cnt;
int n,m,s;

inline void add(int u,int v,int d)
{
	cnt++;
	e[cnt].dis = d;
	e[cnt].to = v;
	e[cnt].next = head[u];
	head[u] = cnt;
}

struct node{
	int index,dist;
	node(int _index=0,int _dist=0):index(_index),dist(_dist){}
	bool operator < (const node &x) const
	{
		return dist > x.dist;
	}
};

priority_queue <node> q;

inline void dij()
{
	dis[s] = 0;
	q.push(node(s,0));
	
	while(!q.empty())
	{
		node t = q.top();
		q.pop();
		int x = t.index, d = t.dist;
		if(dis[x] < d)	continue;

		for(int i = head[x]; i; i = e[i].next)
		{
			int y = e[i].to;
			if(dis[y] > dis[x] + e[i].dis)
			{
				dis[y] = dis[x] + e[i].dis;
				q.push(node(y,dis[y]));
			}
		}
	}
}

int main()
{
	scanf("%d%d%d",&n,&m,&s);
	for(int i = 1; i <= n; i++)
		dis[i] = INF;
	for(int i = 0; i < m; i++)
	{
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w);
	}
	dij();
	for(int i = 1; i <= n; i++)
		printf("%d ",dis[i]);
	return 0;
}