最短路径 Dijkstra

邻接矩阵版

const int N = 510, INF = 0x3f3f3f3f;
int G[N][N], d[N], n, m, a, b, c;
bool visited[N];
int Dijkstra(int s)
{
   
    // fill(d, d + N, INF);		// 初始化到各点的最短距离
    memset(d, 0x3f, sizeof d);
    d[s] = 0;					// s为出发点
    for(int i = 1; i <= n; ++i)
    {
   
        int u = -1;				// 寻找此时已更新的最短距离最小的点
        for(int j = 1; j <= n; ++j)
            if(visited[j] == false && (u == -1 || d[j] < d[u]))
                u = j;
        visited[u] = true;		// 更新u所能到达的点的最短距离
        for(int v = 1; v <= n; ++v)
            if(visited[v] == false && G[u][v] != INF && G[u][v] + d[u] < d[v])
                d[v] = d[u] + G[u][v];
    }							// d[n]为INF则不存在最短路径，无法到达
    return d[n] == INF ? -1 : d[n];
}
int main()
{
   
    cin >> n >> m;
    fill(G[0], G[0] + N * N, INF);
    // memset(G, 0x3f, sizeof(G));
    while(m--)
    {
   
        cin >> a >> b >> c;	
        G[a][b] = min(G[a][b], c); // 可能存在的重边，取权值最小的边
    }
    cout << Dijkstra(1);
    return 0;    
}

邻接表版

const int N = 1e5 + 10, INF = 0x3f3f3f3f;
int h[N], e[N], ne[N], w[N], n, m, idx = 0, d[N];
bool visited[N];
void add(int a, int b, int c)
{
   
    e[idx] = b; ne[idx] = h[a]; w[idx] = c; h[a] = idx++;
}
int Dijkstra(int s)
{
   
    fill(d, d + N, INF);	// 初始化到各点的最短距离
    d[s] = 0;
    for(int i = 1; i <= n; ++i)
    {
   
        int u = -1;			// 寻找此时已更新的最短距离最小的点
        for(int j = 1; j <= n; ++j)
            if(visited[j] == false && (u == -1 || d[j] < d[u]))
                u = j;
                
        visited[u] = true;	// 更新u所能到达的点的最短距离
        for(int v = h[u]; v != -1; v = ne[v])
        {
   
            int j = e[v];
            if(visited[j] == false && w[v] + d[u] < d[j])
                d[j] = w[v] + d[u];
        }
    }					    // d[n]为INF则不存在最短路径，无法到达
    return d[n] == INF ? -1 : d[n];
}

int main()
{
   
    fill(h, h + N, -1);
    cin >> n >> m;
    for(int i = 0; i < m; ++i)
    {
   
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }
    cout << Dijkstra(1);
    return 0;    
}