(note sorting is not completed) [graph theory: find the shortest path of single source]

There are four algorithms for finding the shortest path of a graph

---

The template questions ：

1.（ The data is weak ） Luogu P3371 【 Templates 】 Single source shortest path （ Weak version ）

Title Description

As the title , Let's give a digraph , Please output the shortest path length from one point to all points .

Input format

The first line contains three integers  n,m,s, The number of points 、 The number of directed edges 、 The number of the starting point .

Next m Each row contains three integers  u,v,w, It means one u→v Of , The length is w The edge of .

Output format

Output one line n It's an integer , The first i A means s To the first i The shortest path of a point , If it cannot be reached, output 231−1.

I/o sample

Input #

4 6 1
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4

Output #1

0 2 4 3

explain / Tips

【 Data range 】
about  20%  The data of ：1≤n≤5,1≤m≤15;
about  40%  The data of ：1≤n≤100,1≤m≤104;
about  70%  The data of ：1≤n≤1000,1≤m≤105;
about 100%  The data of ： 1≤n≤104, 1≤m≤5×105,1≤u,v≤n,w≥0, w< 2^{31}, Make sure the data is random .

For the real  100%  The data of , Please move P4779. Please note that , The data range of this question is slightly different from that of this question .

Sample explanation ：

picture 1 To 3 and 1 To 4 Change the position of the text

---

  This question cannot be passed by using adjacency matrix , A chained forward map should be used

①Dijkstra Algorithm

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
int n,m,s;
const int maxn=1e7+5;
const int INF=0x3f3f3f3f;

struct node
{
int to,next,w;
}edge[maxn<<1];
int head[maxn],num=0,dist[maxn];
bool flag[maxn];  // Mark whether the point passes 

inline int read()
{
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9')
	{
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		x=(x<<3)+(x<<1)+(c^48);
		c=getchar();
	}
	return x*f;
}

inline void maketree(int u,int v,int w)  // Chain forward star map 
{
	edge[++num].to=v;
	edge[num].w=w;
	edge[num].next=head[u];
	head[u]=num;
}

inline void dij(int u)  // Algorithm implementation core 
{
	memset(dist,INF,sizeof(dist)); // Assign maximum , As usual Min=99999999 The same idea 
	dist[u]=0;  // The distance from the origin to itself is 0;
	for(int i=1;i<=n-1;++i)
	{
		int temp=0; 
		for(int j=1;j<=n;++j)
		{
			if(!flag[j] && dist[j]<dist[temp])
 	//dist[] Initialize to maximum , from temp=0 Start comparing 
			{
				temp=j; // Change subscript to node serial number 
			}
		}
		flag[temp]=true; // Mark the points you pass 

		for(int k=head[temp];k;k=edge[k].next) 
						// Image reading template of chain forward star 
		{
		int road=edge[k].to;
		dist[road]=min(dist[road],dist[temp]+edge[k].w);
		// Relaxation steps , Maybe adding this point can make the distance smaller 
		}	
	}
}

int main()
{
	n=read(); m=read(); s=read();	
	for(int i=1;i<=m;++i)
	{
		int u=read(),v=read(),w=read();
		maketree(u,v,w);
	}
	dij(s);
	for(int i=1;i<=n;++i) 
	{
		if(dist[i]==INF) cout<<2147483647<<" "; // Something is not connected 
		else cout<<dist[i]<<" ";
	}
	return 0;
}

---

（STL Heap optimization in doubt ）2. Luogu P4779 【 Templates 】 Single source shortest path （ The standard version ）

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn=1e7+5,INF=2147483647;
struct node{
	int to,next,w;
}edge[maxn<<1];

int n,m,s,num=0,head[maxn];
long long int dis[maxn];
bool vis[maxn];
// there STL Not really understood 
struct node1{
	int ans,id; //ans That is to say, the distance to reach this point is ,id Indicates the node number 
	bool operator <(const node1&x) const // Overload operator 
	{
		return x.ans < ans;
	}
};
priority_queue <node1> q;

inline int read()
{
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9')
	{
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		x=(x<<3)+(x<<1)+(c^48);
		c=getchar();
	}
	return x*f;
}

inline void maketree(int u,int v,int w) // Chain forward star map 
{
	edge[++num].to=v;
	edge[num].w=w;
	edge[num].next=head[u];
	head[u]=num;
}

inline void dij()
{
	int u;
	dis[s]=0; // The distance from the origin is 0
	q.push((node1){0,s}); // Put the distance and node number in the queue 
	while(!q.empty())
	{
		node1 tmp=q.top(); 
		u=tmp.id;
		q.pop();
		if(vis[u]) continue;
		vis[u]=true; // If the current point has not passed before 
		for(int i=head[u];i!=-1;i=edge[i].next) // Traverse the points connected to this point 
		{
			int v=edge[i].to;
			if(dis[v]>dis[u]+edge[i].w) // If the new point is shorter than the original path 
			{
				dis[v]=dis[u]+edge[i].w; // Update data , Slack operation 
				if(!vis[v])  
				{
					q.push((node1){dis[v],v}); // Then find the next point through this point 
				}
			}
		}
	}
	
	for(int i=1;i<=n;++i)
	{
		printf("%d ",dis[i]);
	}
}

int main()
{
	n=read(); m=read(); s=read();
	memset(head,-1,sizeof(head));
	
	for(int i=1;i<=m;++i)
	{
		int u=read(),v=read(),w=read();
		maketree(u,v,w);
	}
	
	for(int i=1;i<=n;++i)
	{
		dis[i]=INF;
	}
	dij();
	return 0;
}

---

Related exercises ：1. Luogu P1629 The postman delivers the mail

Ideas ：

1. Create two diagrams , The first figure is the input figure , The second picture is the reverse picture obtained after turning .

2. The sum of all paths is the shortest , The o ： from 1 Solstice i , The road you took when you went and the road you took when you came back are the shortest path this time , That is to find the shortest path of two graphs to each point respectively

---

  The code is as follows ：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
using namespace std;
int n,m,res=0;
const int maxn=1e7+5,INF=0x3f3f3f3f;

struct node{
	int to,next,w;
}edge[maxn<<1];
int num=0,head[maxn],dis[maxn];
bool vis[maxn];

struct node2{
	int to,next,w;
}edge1[maxn<<1];
int num1=0,head1[maxn],dis1[maxn];
bool vis1[maxn];

struct node1{
	int ans,num;
	bool operator < (const node1&x) const
	{
		return x.ans < ans;
	}
};
priority_queue <node1> q;

struct node3{
	int ans,num;
	bool operator < (const node3&x) const
	{
		return x.ans < ans;
	}
};
priority_queue <node3> q2;

inline int read()
{
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9')
	{
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		x=(x<<3)+(x<<1)+(c^48);
		c=getchar();
	}
	return x*f;
}

inline void write(int x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar (x%10+'0');
	return;
}

inline void add(int u,int v,int w) // Input diagram 
{
	edge[++num].to=v;
	edge[num].w=w;
	edge[num].next=head[u];
	head[u]=num;
}

inline void add1(int u,int v,int w) // Reverse diagram 
{
	edge1[++num1].to=v;
	edge1[num1].w=w;
	edge1[num1].next=head1[u];
	head1[u]=num1;
}

inline void dij()
{
	int u;
	dis[1]=0; 
	q.push((node1){0,1});
	while(!q.empty())
	{
		node1 temp=q.top();
		u=temp.num;
		q.pop();
		if(vis[u]) continue;
		vis[u]=true;
		for(int i=head[u];i!=-1;i=edge[i].next)
		{
			int v=edge[i].to;
			if(dis[v]>dis[u]+edge[i].w)
			{
			dis[v]=dis[u]+edge[i].w;
			if(!vis[v]) q.push((node1){dis[v],v});
			}
		}
	}
}

inline void dij1()
{
	int u;
	dis1[1]=0;
	q2.push((node3){0,1});
	while(!q2.empty())
	{
		node3 temp=q2.top();
		u=temp.num;
		q2.pop();
		if(vis1[u]) continue;
		vis1[u]=true;
		for(int i=head1[u];i!=-1;i=edge1[i].next)
		{
			int v=edge1[i].to;
			if(dis1[v]>dis1[u]+edge1[i].w)
			{
			dis1[v]=dis1[u]+edge1[i].w;
			if(!vis1[v]) q2.push((node3){dis1[v],v});
			}	
		}
	}
}

int main()
{
	n=read(); m=read();
	memset(head,-1,sizeof(head));
	memset(head1,-1,sizeof(head1));
	for(int i=1;i<=m;++i)
	{
		int u=read(),v=read(),w=read();
		add(u,v,w);
		add1(v,u,w);
	}
	
	for(int i=1;i<=n;++i)
	{
		dis[i]=INF;
	}
	dij();
	for(int i=2;i<=n;++i)
	{
		res+=dis[i];
	}
	

	for(int i=1;i<=n;++i)
	{
		dis1[i]=INF;
	}
	dij1();
	for(int i=2;i<=n;++i)
	{
		res+=dis1[i];
	}
	write(res);
	return 0;
}

---

2. Luogu P1821 [USACO07FEB] Cow Party S

Ideas ：

This problem needs to pay attention to one detail ：

From the question ： For this n The shortest path for a cow （ One back and forth ） The length of the longest path in .

That is to say, ask for completion from x After the shortest path from point to any other point , Then output the maximum value in these shortest paths . Other implementation methods are similar to Dijkstra Algorithm + The template practice of heap optimization is the same .

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
int n,m,x,ans=0;
const int maxn=1e5+5,INF=0x3f3f3f3f; 
struct node{
	int to,next,w;
}edge[maxn<<1];
bool vis[maxn];
int head[maxn],dis[maxn],num=0;

struct node1{
	int to,next,w;
}edge1[maxn<<1];
bool vis1[maxn];
int dis1[maxn],head1[maxn],num1=0;

struct node2{
	int ans,id;
	bool operator <(const node2&x) const
	{
		return x.ans < ans;
	}
};
priority_queue <node2> q1;

struct node3{
	int ans,id;
	bool operator <(const node3&x) const
	{
		return x.ans < ans;
	}
};
priority_queue <node3> q2;

inline void add(int u,int v,int w)
{
	edge[++num].to=v;
	edge[num].w=w;
	edge[num].next=head[u];
	head[u]=num;
}

inline void add1(int u,int v,int w)
{
	edge1[++num1].to=v;
	edge1[num1].w=w;
	edge1[num1].next=head1[u];
	head1[u]=num1;
}

inline void dij(int x)
{
	int u;
	memset(dis,INF,sizeof(dis));
	dis[x]=0;
	q1.push((node2){0,x});
	while(!q1.empty())
	{
		node2 temp=q1.top();
		u=temp.id;
		q1.pop();
		if(vis[u]) continue;
		vis[u]=true;
		for(int i=head[u];i!=-1;i=edge[i].next)
		{
			int v=edge[i].to;
			if(dis[v]>dis[u]+edge[i].w)
			{
				dis[v]=dis[u]+edge[i].w;
				if(!vis[v]) q1.push((node2){dis[v],v});
			}
		}
	}	
}

inline void dij1(int x)
{
	int u;
	memset(dis1,INF,sizeof(dis1));
	dis1[x]=0;
	q2.push((node3){0,x});
	while(!q2.empty())
	{
		node3 temp=q2.top();
		u=temp.id;
		q2.pop();
		if(vis1[u]) continue;
		vis1[u]=true;
		for(int i=head1[u];i!=-1;i=edge1[i].next)
		{
			int v=edge1[i].to;
			if(dis1[v]>dis1[u]+edge1[i].w)
			{
				dis1[v]=dis1[u]+edge1[i].w;
				if(!vis1[v]) q2.push((node3){dis1[v],v});
			}
		}
	}	
}

inline int read()
{
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9')
	{
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0' && c<='9')
	{
		x=(x<<3)+(x<<1)+(c^48);
		c=getchar();
	}
	return x*f;
}

inline void write(int x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}

int main()
{
	memset(head,-1,sizeof(head));
	memset(head1,-1,sizeof(head1));
	
	n=read();m=read();x=read();
	for(int i=1;i<=m;++i)
	{
		int u=read(),v=read(),w=read();
		add(u,v,w);
		add1(v,u,w);
	}
	
	dij(x);
	dij1(x);
	for(int i=1;i<=n;++i)
	{
		ans=max(ans,dis[i]+dis1[i]); //dis[i]+dis1[i] The value of is already to i Click the shortest path back and forth 
	}
	write(ans);
	return 0;
}

---

3. Luogu P1144 Shortest circuit count

Ideas ： From the question ： Demand from the top  1  To the top  i  How many different shortest paths are there  

Pay attention to the following details ：

1. Undirected power map ： Undirected ： Both positive and negative maps ; Have no right ： Set the edge weight to 1;

2. There is only one way from oneself to oneself （ Self ring ）;

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <queue>
#include <algorithm>
using namespace std;
int n,m;
const int maxn=1e7+5,INF=0x3f3f3f3f;
struct node{
	int to,next;
}edge[maxn<<1];

struct node2{
	int ans,id;
	bool operator < (const node2&x) const
	{
		return x.ans < ans;
	}
};
int num=0,head[maxn],dis[maxn],ans[maxn];
bool vis[maxn];
priority_queue <node2> q;

inline int read()
{
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9')
	{
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0' && c<='9')
	{
		x=(x<<3)+(x<<1)+(c^48);
		c=getchar();
	}
	return x*f;
}

inline void write(int x)
{
	if(x>9) write(x/10);
	putchar(x%10+'0');
}

inline void add(int u,int v)
{
	edge[++num].to=v;
	edge[num].next=head[u];
	head[u]=num;
}

inline void dij()
{
	memset(dis,INF,sizeof(dis));	
	int u;
	ans[1]=1; // Because there is a self ring , It's also a way to go by yourself 
	dis[1]=0;
	q.push((node2){0,1});
	while(!q.empty())
	{
		node2 temp=q.top();
		u=temp.id;
		q.pop();
		if(vis[u]) continue;
		vis[u]=true;
		for(int i=head[u];i!=-1;i=edge[i].next)
		{
			int v=edge[i].to;
			if(dis[v]>dis[u]+1) // The first i The shortest path of the point can be updated but has not been updated 
			{
			dis[v]=dis[u]+1; // to update 
			ans[v]=ans[u]%100003; // You can only come to this stage from the previous node 
			if(!vis[v]) q.push((node2){dis[v],v});
			}

			else if(dis[v]==dis[u]+1) // If you pass the last u Point to v Point is already the shortest path 
			{
				ans[v]+=ans[u]; // Plus it can reach the point v The point of u All situations of 
				ans[v]=ans[v]%100003;
			}
		}	
	}
}

int main()
{
	n=read(); m=read();
	memset(head,-1,sizeof(head));
	memset(ans,0,sizeof(ans));
	for(int i=1;i<=m;++i)
	{
		int u=read(),v=read();
		add(u,v); add(v,u);
	}
	dij();
	for(int i=1;i<=n;++i)
	{
		write(ans[i]);
        putchar('\n');	
	}
	return 0;
}