HDU 1385 Minimum Transport Cost(多源最短路径+路径记录)

p[i][j]记录从i到j的路径上的下一个结点(后继)，修改最短路时更新即可。

void floyd()
{
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(map[i][j]>map[i][k]+map[k][j]+b[k]){
                    map[i][j]=map[i][k]+map[k][j]+b[k];
                    h[i][j]=h[i][k];
            }
            else if(map[i][j]==map[i][k]+map[k][j]+b[k]){//路径长度相同要求字典序最小
                if(h[i][j]>h[i][k])
                    h[i][j]=h[i][k];
            }
}

拓展：若要求记录前驱结点则修改为h[i][j]=h[k][j].