Dijkstra find the shortest path

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^5,
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

  Description by topic , The total is n A little bit ,m side ,n,m The data range of is greater than 100 times , Belong to A dense picture , And all edge weights in the graph are positive , So we can use it simple Dijkstra Algorithm To find the shortest path problem

Dense graphs use Adjacency matrix for storage And every point is initially infinite

Use an array to store 1 The shortest path to this location

Use one bool An array of types , To determine whether the location has been determined as the shortest path

Update the path from each point to the adjacent point in turn every time , And take the minimum

If a double edge occurs , Keep his shortest side

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N=510;
int g[N][N];// Adjacency matrix 
int dis[N];// Store the shortest path 
bool st[N];// Judge whether it has been judged 

int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    for (int i = 0; i < n - 1; i ++ )
    {
        int t = -1;
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        for (int j = 1; j <= n; j ++ )
            dist[j] = min(dist[j], dist[t] + g[t][j]);

        st[t] = true;
    }

    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

int main()
{
    scanf("%d%d", &n, &m);

    memset(g, 0x3f, sizeof g);
    while (m -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);

        g[a][b] = min(g[a][b], c);
    }

    printf("%d\n", dijkstra());

    return 0;
}

GYX