Huomaa, että kaikki tiet ovat kaksisuuntaisia eli ei ole väliä, kummin päin kaupungit annetaan.
Voit olettaa, että kaupunkeja on enintään $50$ ja luokan metodeita kutsutaan enintään $100$ kertaa. Jokaisen tien pituus on kokonaisluku välillä $1 \dots 1000$.
Python
Toteuta tiedostoon
bestroute.py
luokka BestRoute
, jossa on seuraavat metodit:- konstruktori, jolle annetaan kaupunkien määrä
-
add_road
lisää kaupunkien $a$ ja $b$ välille tien, jonka pituus on $x$
-
find_route
ilmoittaa lyhimmän reitin pituuden kaupunkien $a$ ja $b$ välillä (tai $-1$, jos mitään reittiä ei ole)
class BestRoute: def __init__(self,n): # TODO def add_road(self,a,b,x): # TODO def find_route(self,a,b): # TODO if __name__ == "__main__": b = BestRoute(3) b.add_road(1,2,2) print(b.find_route(1,3)) # -1 b.add_road(1,3,5) print(b.find_route(1,3)) # 5 b.add_road(2,3,1) print(b.find_route(1,3)) # 3Java
Toteuta tiedostoon
BestRoute.java
luokka BestRoute
, jossa on seuraavat metodit:- konstruktori, jolle annetaan kaupunkien määrä
-
addRoad
lisää kaupunkien $a$ ja $b$ välille tien, jonka pituus on $x$
-
findRoute
ilmoittaa lyhimmän reitin pituuden kaupunkien $a$ ja $b$ välillä (tai $-1$, jos mitään reittiä ei ole)
public class BestRoute { public BestRoute(int n) { // TODO } public void addRoad(int a, int b, int x) { // TODO } public int findRoute(int a, int b) { // TODO } public static void main(String[] args) { BestRoute b = new BestRoute(3); b.addRoad(1,2,2); System.out.println(b.findRoute(1,3)); // -1 b.addRoad(1,3,5); System.out.println(b.findRoute(1,3)); // 5 b.addRoad(2,3,1); System.out.println(b.findRoute(1,3)); // 3 } }