2021-01-23
摸了两天…嘻嘻
今天是康复链式前向星和dijkstra的一天。

洛谷模板题
https://www.luogu.com.cn/problem/P4779
链式前向星参考：
https://blog.****.net/sugarbliss/article/details/86495945
链式前向星其实就是静态建立的邻接表，时间效率为O（m），空间效率也为O（m）。遍历效率也为O（m）。怪厉害的。

那么dijkstra就是单源最短路的一种算法。
流程：
dis：出发点到这个点的距离。

1. 初始化每个点的距离，出发点为0，其余值为无穷大。
2. 找到一个dis值最小的未确定最短路径的点x，将它确定。
3. 然后将所有x的出边能到的点的dis更新，若dis[y]>dis[x]+z,则令dis[y]=dis[x]+z
4. 重复2、3步，直到所有的点都确定。

dijkstra的堆优化：
我们可以使用优先队列将第二步优化，直接取dis最小的点。

#include<bits/stdc++.h>
using namespace std;
const int maxn=500010;
struct Edge
{
    int to, dis, next;
}e[maxn];
int head[100010],dis[100010], cnt,s,m,n,u1,v1,w1;
bool vis[100010];
struct node{
	int dis;
	int pos;
	bool operator <(const node &x)const{
		return x.dis<dis;	
	}
};
priority_queue <node> q;
void add_edge(int u,int v,int w){
	cnt++;
	e[cnt].to=v;
	e[cnt].dis=w;
	e[cnt].next=head[u];
	head[u]=cnt;
}
void dijkstra(){
	dis[s]=0;		
	q.push((node){0,s}) ;
	while(!q.empty()){
		node temp=q.top();
		q.pop();
		int x=temp.pos;
		int d=temp.dis;
		if(vis[x])continue;
		vis[x]=1;
		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;
				if(!vis[y])
				q.push((node){dis[y],y});
			}
		}
	}
}
int main(){
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++){
		cin>>u1>>v1>>w1;
		add_edge(u1,v1,w1);
	}
	for(int i = 1; i <= n; i++)
	dis[i]=0x3f3f3f3f;
	dijkstra();
	for( int i = 1; i <= n; i++ )
        printf( "%d ", dis[i] );
    return 0;
}

链式前向星好用！冲，成为图论选手！