图论——最短路——dijstra

1   流程

    dist[所有点] = +∞
    dist[起始点] = 0

    for( n 次循环 )
    {
        找出未被标记的节点中dist最小的节点t
        st[t] = true
        用t更新其他所有出点
    }

    判断是否能走

2   code

    int dijstra( int u )
    {
        memset( dist, 0x3f, sizeof dist );
        dist[u] = 0;

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

            st[t] = true;

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

        }

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