迪杰特斯拉（链式前向星优化）

发现迪杰特斯拉的优化过一段时间不写就直接忘光光了，写个博客加深一下印象（这里默认是有向图模板）

基础的迪杰特斯拉就不写了，只写优化

首先是这部分

void add(int x,int y,int z){
	to[++count1]=y;
	v[count1]=z;
	nex[count1]=fr[x];
	fr[x]=count1;
}
           

这个是记录所有单条能走通的路的，to数组代表去往哪里，v数组代表这条路的权值，nex数组是表示下一个节点的位置，fr数组表示前一个这个节点能过的路，你看到看不明白很正常，我给你举个例子你就明白了

假设我们现在有4个城市，4条路

这4条路分别是

1 2 2

2 3 2

2 4 1

1 3 5

我们先看有城市1的路，并结合上面的add函数，有

to [ 1 ] =2

v [ 1 ] = 2

nex [ 1 ] = 0

fr [ 1 ] = 1 //这是第一条路

to [ 4 ] = 3

v [ 4 ] = 5

nex [ 4 ] = 1

fr [ 1 ] = 4 //这是第二条路

根据这两路我们不难看出来，fr函数是在不断更新的，它始终保留的是数据中最后出现的有这个城市的路的位置，而我们保存上一条路的就是nex函数，就拿例子来说，一开始nex [ 1 ] = 0 ,表示这是1城市能走到的最后一条路了 ，而fr [ 1 ] 一开始 = 1 表示上一条有1城市的路是1号路，然后到下一条有城市1的路时，nex [ 4 ] =fr [ 1 ] = 1表示上一条有城市1的路是一号路，fr [ 1 ] 此时就等于4了，表示最后一条有城市1的路是4号路 ，换言之，我们把输入的顺序按照这个逻辑反过来，就能走过所有有1城市的路，其他城市同理

这个代码是从城市1到所有其他城市的最短路模板

P4779 【模板】单源最短路径（标准版）

#include<iostream>
#include<cstdio>
#include<cmath>
#include<queue>
#define M(x,y) make_pair(x,y)
using namespace std;
const int maxn=100010;
int fr[maxn],nex[maxn*2],to[maxn*2],v[maxn*2],dist[maxn],vis[maxn],count1=0;
priority_queue< pair<int,int> > q;
int n,m,s;
void add(int x,int y,int z){
	to[++count1]=y;
	v[count1]=z;
	nex[count1]=fr[x];
	fr[x]=count1;
}
int main(){
	int x,y,z;
	s=1;
	cin>>n>>m;
	for(int i=0;i<m;i++){
		scanf("%d %d %d",&x,&y,&z);
		add(x,y,z);
	}
	for(int i=1;i<=n;i++) dist[i]=1e10;
	dist[s]=0;
	q.push(M(0,s));
	while(!q.empty()){
		int t=q.top().second;
		q.pop();
		if(vis[t]){
			continue;
		}
		vis[t]=1;
		for(int i=fr[t];i;i=nex[i]){
			int target1=to[i];
			if(dist[target1]>dist[t]+v[i]){
				dist[target1]=dist[t]+v[i];
				q.push(M(-dist[target1],target1));
			}
		}
	}
	for(int i=1;i<=n;i++){
		printf("%d ",dist[i]);
	}
	return 0;
}
           

这个是从城市1到城市n的最短路积，其中的f数组和ll数组与上面的nex数组同理，记录从城市1到城市n的最短路径进行运算

P2384 最短路

#include<iostream>
#include<cstdio>
#include<cmath>
#include<queue>
#define M(x,y) make_pair(x,y)
using namespace std;
const int maxn=100010;
int fr[maxn],nex[maxn*2],to[maxn*2],v[maxn*2],vis[maxn],count1=0,f[maxn],ll[maxn];
double dist[maxn];
priority_queue< pair<int,int> > q;
int n,m,s;
void add(int x,int y,int z){
	to[++count1]=y;
	v[count1]=z;
	nex[count1]=fr[x];
	fr[x]=count1;
}
int main(){
	int x,y,z;
	s=1;
	cin>>n>>m;
	for(int i=0;i<m;i++){
		scanf("%d %d %d",&x,&y,&z);
		add(x,y,z);
	}
	for(int i=1;i<=n;i++) dist[i]=1e10;
	dist[s]=0;
	q.push(M(0,s));
	while(!q.empty()){
		int t=q.top().second;
		q.pop();
		if(vis[t]){
			continue;
		}
		vis[t]=1;
		for(int i=fr[t];i;i=nex[i]){
			int target1=to[i];
			if(dist[target1]>dist[t]+log10(v[i])){
				dist[target1]=dist[t]+log10(v[i]);
				q.push(M(-dist[target1],target1));
				f[target1]=t;
				ll[target1]=v[i];
			}
		}
	}
	long long ans=1;
	for (int i=n;i!=1;i=f[i])
		ans=ans*ll[i]%9987;
	printf("%lld",ans);
	return 0;
}