P3371 [template] single source shortest path (weakened version)

Background

The test data is random data , In the exam, there may be structured data that makes SPFA Not through , If necessary, please move  P4779.

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,sn,m,s, The number of points 、 The number of directed edges 、 The number of the starting point .

Next  mm  Each row contains three integers  u,v,wu,v,w, It means one  u \to vu→v  Of , The length is  ww  The edge of .

Output format

Output one line  nn  It's an integer , The first  ii  A means  ss  To the first  ii  The shortest path of a point , If it cannot be reached, output  2^{31}-1231−1.

I/o sample

Input #1 Copy

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

Output #1 Copy

0 2 4 3

explain / Tips

【 Data range 】
about  20\%20%  The data of ：1\le n \le 51≤n≤5,1\le m \le 151≤m≤15;
about  40\%40%  The data of ：1\le n \le 1001≤n≤100,1\le m \le 10^41≤m≤104;
about  70\%70%  The data of ：1\le n \le 10001≤n≤1000,1\le m \le 10^51≤m≤105;
about  100\%100%  The data of ：1 \le n \le 10^41≤n≤104,1\le m \le 5\times 10^51≤m≤5×105,1\le u,v\le n1≤u,v≤n,w\ge 0w≥0,\sum w< 2^{31}∑w<231, Make sure the data is random .

For the real  100\%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 problem needs to use the chain forward star

This is ok  【AgOHの data structure 】 Do you really know chain forward stars ？_ Bili, Bili _bilibili

 

  Edge storage

In this way, you only need to open an array to store the first edge of each point , Then store each point as the starting point of each edge , In this way, we can achieve no repetition and no leakage .

In the chained forward star map , We need to define a structure ：

struct EDGE 
{
    int next;
    int to;
}edge[1000000];

And an array ：

int head[1000000];

And a variable ：

int cnt=0;// The pointer 

You will find that there is no starting point ！！ In fact, the starting point is to use headhead Deposited

give an example ：

Pictured ： Such a directed graph , Input is ：

1 2
1 3
1 4
2 3

Step by step analysis ：

1. Input 1 2, representative 1 Even to the 2.

cnt++;// As the subscript of the structure , It makes no sense 
head[1]=cnt;// node 1 My first son exists edge[cnt] Inside 
edge[cnt].to=2; node 1 My son is 2

here ： cnt=1cnt=1

edgeedge	cnt=1cnt=1	cnt=2cnt=2	cnt=3cnt=3	cnt=4cnt=4
toto	22	00	00	00
nextnext	00	00	00	00

headhead	Subscript =1=1	Subscript =2=2	Subscript =3=3	Subscript =4=4
value	11	00	00	00

2. Input 1 3, representative 1 Even to the 3.

cnt++;
head[1]=cnt;
edge[cnt].to=3; node 1 My son is 3
// At this time ,3 Become a node 1 Son , however 2 Pushed down ...
// So it should be introduced into the structure next Elements , Record ：3 And a brother （next） yes 2
// So the code should be changed to ：
cnt++;
edge[cnt].to=3;// node 1 Even to the 3
edge[cnt].next=head[1];//3 My brother is 2
head[1]=cnt;// to update head

here ： cnt=2cnt=2

edgeedge	cnt=1cnt=1	cnt=2cnt=2	cnt=3cnt=3	cnt=4cnt=4
toto	22	33	00	00
nextnext	00	11	00	00

headhead	Subscript =1=1	Subscript =2=2	Subscript =3=3	Subscript =4=4
value	22	00	00	00

3. Input 1 4, representative 1 Even to the 4.

here ： cnt=3cnt=3

edgeedge	cnt=1cnt=1	cnt=2cnt=2	cnt=3cnt=3	cnt=4cnt=4
toto	22	33	44	00
nextnext	00	11	22	00

headhead	Subscript =1=1	Subscript =2=2	Subscript =3=3	Subscript =4=4
value	33	00	00	00

4. Input 2 3, representative 2 Even to the 3.

here ： cnt=4cnt=4

edgeedge	cnt=1cnt=1	cnt=2cnt=2	cnt=3cnt=3	cnt=4cnt=4
toto	22	33	44	33
nextnext	00	11	22	00

headhead	Subscript =1=1	Subscript =2=2	Subscript =3=3	Subscript =4=4
value	33	44	00	00

Be careful ：edge[cnt].nextedge[cnt].next  and head[1]head[1] All stored are structural subscripts （ namely cntcnt Value ） To access the number of the edge pointed to , Use them separately edge[edge[cnt].next].toedge[edge[cnt].next].to,edge[head[1]].toedge[head[1]].to

If you need to record the weight , Add an element to the structure

Code ：( Weighted ）

#include<iostream>
using namespace std;
struct edge 
{ 
    int next;
    int to;
    int wei;
}edge[MAXM];
int head[MAXN];//head[i] by i The first side of the dot 
int cnt=0;
void addedge(int u,int v,int w) // The starting point , End , A weight  
{
    edge[++cnt].next=head[u];// to update cnt
    edge[cnt].to=v;
    edge[cnt].w=w;
    head[u]=cnt;
}
int main()
{
	int n;
    for(int i=1;i<=n;i++)
    {
    	int a,b,wei;
        addedge(a,b,wei);
        // If it's an undirected graph , still more addedge(b,a,wei);
    }
}

Be careful ：

there next It refers to the next edge when traversing ,head It refers to the first side when traversing , While saving edges is equivalent to reverse operation , therefore next Record the previous side , and head Record the last edge .

---

Traversal of edges

In traversal to x For all edges of the starting point , Just like this

	for(int i=head[x];i!=0;i=edge[i].next)

The end condition of this cycle is i be equal to 0, Because the last side , That is, the first edge when saving edges , In the head The value is saved in next when ,head Not updated yet , That is to say 0. So when next return 0 when , It means that these edges are traversed .

---

Advantages and characteristics

You can save pictures , You can also save trees , Compared with adjacency matrix , The spatial complexity of a chained forward star is O（n）, Save a lot of storage space , Because edge storage saves a lot of two boundless space . And when traversing , Those points that are connected to the starting point without edge do not need to be processed , It can be said that time and space are dominant , This is being OIer The reason why they are widely used .

#include<bits/stdc++.h>
using namespace std;
#define inf 2147483647
#define N 10005
#define M 500005
int n,m,s;
int low[N];// distance 
int vis[N];// Tag array 
int head[N],cnt;// Save from 

struct node
{
    int to,v,next;
} e[M];

// Bordering 
void add(int a,int b,int v)
{
    cnt++;
    e[cnt].to=b;
    e[cnt].v=v;
    e[cnt].next=head[a];///next Record the previous side 
    head[a]=cnt;///head Record the last edge 
}
//Dijkstra
void Dij()
{
    int idx = s;
    low[s]=0;// The distance from oneself to oneself is 0
    while(true)
    {
        int idx=-1;
        int Min=inf;
        for(int i=1; i<=n; i++)
        {
            if(vis[i] == 0 && low[i]<Min)
            {
                Min=low[i];
                idx=i;
            }
        }
        if(idx == -1)break;// It means that there is no point that has not been traversed 
        vis[idx] = 1;
        for(int i=head[idx]; i!=0; i=e[i].next)
        {
            int a=idx,b=e[i].to,v=e[i].v;// Notice here a=idx
            if(low[b]>low[a]+v)// It's a greater than sign. Don't write it as a less than sign 
                low[b]=low[a]+v;
        }
    }
    for(int i=1; i<=n; i++)
        cout<<low[i]<<" ";
}
int main( )
{
    cin>>n>>m>>s;
    for(int i=1; i<=n; i++)
        low[i]=inf;
    for(int i=1; i<=m; i++)
    {
        int a,b,v;
        cin>>a>>b>>v;
        add(a,b,v);
    }
    Dij();
    return 0;
}