Search and graph theory: Dijkstra finding the shortest path i-dijkstra (shortest path)

subject ：AcWing 849. Dijkstra Find the shortest path I
Given a n A little bit m Directed graph of strip edge , There may be double edges and self rings in the graph , All edge weights are positive .

Please find out 1 It's on the n The shortest distance of point No , If you can't get from 1 Go to No n Number point , The output −1.

Input format
The first line contains integers n and m.

Next m Each row contains three integers x,y,z, Indicates that there is a from point x point-to-point y The directed side of , Side length is z.

Output format
Output an integer , Express 1 It's on the n The shortest distance of point No .

If the path doesn't exist , The output −1.

Data range
1≤n≤500,
1≤m≤10⁵,
The side length involved in the figure does not exceed 10000.

sample input ：

3 3
1 2 2
2 3 1
1 3 4

sample output ：

3

Simple dijastra algorithm ：
Conduct n Secondary cycle ,
1. First step ： Find an undetermined point , And closest to the starting point （ greedy ） Prove slightly
2. The second step ： Update all remaining points to the current point , Because many points can reach the starting point through this point .
3. The third step ： Mark this point as a definite point

#include <iostream>
#include <cstring>
using namespace std;

const int N = 510;
int g[N][N]; //  Adjacency matrix 
int dist[N]; //  Shortest path 
bool st[N]; //  Judge whether the point is the shortest 
int n,m;

int dijkstra()
{
    
    memset(dist,0x3f,sizeof(dist));
    dist[1]=0; //  The distance of the first point is 0
    
    for(int i=0;i<n-1;i++)
    {
    
        int t=-1;
        for(int j=1;j<=n;j++) //  Find an undetermined point , And closest to the starting point （ greedy ）
            if(!st[j]&&(t==-1||dist[t]>dist[j]))
                t=j;
        
        for(int j=1;j<=n;j++) //  Update the distance between all points and the current point 
            dist[j]=min(dist[j],dist[t]+g[t][j]);
            
        st[t]=true; //  Set the current point as the determined point 
    }
    if(dist[n]==0x3f3f3f3f)return -1;
    return dist[n];
}
int main()
{
    
    cin>>n>>m;
    memset(g,0x3f,sizeof(g)); //  Initialization distance 
    
    while(m--)
    {
    
        int a,b,c;
        cin>>a>>b>>c;
        g[a][b]=min(g[a][b],c); //  Ensure that the adjacency matrix is the shortest distance 
    }
    
    int k=dijkstra();
    cout<<k<<endl;
    return 0;
}