This is only an attempt to answer the question, if I understood it correctly. You want to "cover the actual road connection between cities (...) based on the GoogleMap".
First step: find the coordinates of the two cities you want to use as edges in your graphic:
c1 = CityData["Uppsala", "Coordinates"]
c2 = CityData["Marsta", "Coordinates"]
{59.86, 17.64}
{59.63, 17.84}
Second step: define the center of the map:
center = (c1 + c2)/2
{59.745, 17.74}
Third step: Import[]
the actual Google Maps image based on the center you've specified
g1=Import["http://maps.google.com/maps/api/staticmap?center="<>ToString[center[[1]]]<>"," <>ToString[center[[2]]]<>"&zoom=10&size=400x400&sensor=false&maptype=roadmap"]
I'm still wondering what exactly you want with "set the calculated distance as EdgeCost value of created edge"...
EDITED
After some research, I think it can also be done:
Define the cities:
from = ToString[c1[[1]]] <> "," <> ToString[c1[[2]]];
to = ToString[c2[[1]]] <> "," <> ToString[c2[[2]]];
Now use Mathematica to import data from Google with distance and time:
distdata = Import["http://maps.googleapis.com/maps/api/directions/json?origin=" <> from <> "&destination=" <> to <> "®ion=es&sensor=false", {"HTML", "Source"}];
Now find distance by road:
roadDistance = StringSplit[StringSplit[distdata, ":"][[13]],","][[1]]
"35.3 km"
Now find travel time:
travelTime = StringSplit[StringSplit[distdata, ":"][[16]], ","][[1]]
"30 mins"
EDITED
Now put everything together.
First define graphic with markers...
Import["http://maps.google.com/maps/api/staticmap?center=" <>ToString[center[[1]]] <> "," <> ToString[center[[2]]] <> "&zoom=10&size=400x400&sensor=false&maptype=roadmap&markers=color:blue%7Clabel:O%7C" <> ToString[c1[[1]]] <> "," <> ToString[c1[[2]]] <>"&markers=color:red%7Clabel:D%7C" <> ToString[c2[[1]]] <> "," <> ToString[c2[[2]]]]
and
{roadDistance,travelTime}
{"35.3 km","30 mins"}