What is easiest way to implement a graph of strings(cities)?

I have already implemented a adjacency matrix graph which uses just integers types.(consider C++ for everything that I talk here)

And know I'm implementing another graph that will receive cities in the vertexes and distances in the edges, using my old implementation, then I was wondering if this is a good idea or I should use a different implementation for this problem(like linked lists). The idea here is to read all the cities and their distances to each other from a txt file, add it in the graph and then display a menu to the user so he/she can consult the distance from city A to B and get a list of all the cities he need to travel before reach the target.

I'm planning to read the city, give it a number code, and add it in the graph, instead of adding the string "city" (would need to convert the graph from integer to string)

What do you think,any idea/advice?