char * campo;
    char ** datos;
    int filas=0;
    int MaxLinea=maxLinea;
    char lineaFinal[maxLinea];
    char linea[maxLinea];
    datos=malloc(sizeof(char*)*1);
    datos=malloc(sizeof(char)*3);
 
    // se lee cada fila de todo el fichero de elementos
    while(fgets(linea,MaxLinea,fichero) >0 )
    {
            strcpy(lineaFinal[filas],linea);
            filas++;
            datos=realloc(datos,sizeof(char*)*filas);
    }
 
    for(int i=0; i<filas; i++)
    {
        datos=realloc (datos,sizeof(char)*3);
    }
 
    for(int i=0; i<filas; i++)
    {
        for(int j=0; j<3; j++)
 
        {
            campo = strtok(lineaFinal[filas], " ");
            datos[i][j]=campo;
            campo=strtok(NULL," ");
            datos[i][j]=campo;
            campo=strtok(NULL," ");
            datos[i][j]=campo
        }
    }
 

• Si sabes la cantidad y nombre de ciudades que hay, en tiempo de compilación
  En este caso podrías crear otra struct que relacione cada ciudad con un índice (simulando un Map)
  

typedef struct {
  int indice;
  char *nombre;
} Ciudad;
 
const int NUM_CIUDADES = 3;
 
int main() {
  Ciudad ciudades[NUM_CIUDADES] = { // NUM_CIUDADES aqui es opcional
    {0, "Ciudad 1"},
    {1, "Ciudad 2"},
    {2, "Ciudad 3"}
  };
 
  float matriz_warshall[NUM_CIUDADES][NUM_CIUDADES];
 
  while(fscanf(f, "%s %s %f", ciudad_origen, ciudad_destino, distancia) === 3) {
    // Cada vez que leas una linea, tienes que buscar a que indices corresponden esas ciudades
    int indice_origen = buscarIndice(ciudades, NUM_CIUDADES, ciudad_origen);
    int indice_destino = buscarIndice(ciudades, NUM_CIUDADES, ciudad_destino);
    // Y asi sabras en que posicion tienes que guardar esa distancia
    matriz_warshall[indice_origen][indice_destino] = distancia;
    // Y si el grafo es bidireccional:
    matriz_warshall[indice_destino][indice_origen] = distancia;
  }
  ...
} 

• Si no conoces las ciudades en tiempo de compilación (la cosa se complica un poco más)
  Aquí podrás usar un struct como en el caso anterior pero no podrás inicializar el array ciudades[] estáticamente.
  Cada vez que leas una ciudad, tendrás que ver si ya la tienes guardada en el array y coger su índice correspondiente. En caso de no encontrarla en el array, tendrás que añadirla al final con su índice correspondiente. Hecho esto, la solución es igual al caso anterior.