1.最短路

int dijkstra()
{
    // chushihua
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    for (int i = 1; i < n; i++)
    {
        int t = -1;
        for (int j = 1; j < n; j++)
            if (!found[j] && (t == -1 || dist[j] < dist[t]))
                t = j;
        found[t] = 1;
        for (int j = 1; j < n; j++)
            dist[j] = min(dist[j], dist[t] + w[t - 1][j - 1]);
    }
    // for (int i = 1; i < n; i++)
    //     cout << dist[i] << ' ';
    // cout << endl;
    return dist[n - 1];
}