Zadanie Bitocja przyśpieszenie algorytmu (zadanie grafowe)

Question

Mam takie zadanie Bitocja

I mam algorytm z użyciem algorytmu Floyda-Warshalla, niestety mój algorytm jest za wolny, co robię źle ?

#include <bits/stdc++.h>

#define ll long long

const ll INF = 1000000 * 100 + 1;

using namespace std;

class Bitocja{
    int number_of_cities;
    int built_ways;
    int new_ways;
    vector<vector<ll>>graph;
public:
    Bitocja(){
        cin >> number_of_cities >> built_ways >> new_ways;

        graph.resize(number_of_cities + 1, vector<ll>(number_of_cities + 1, INF));

        for (int i = 1; i <= number_of_cities; i++)
            graph[i][i] = 0;
    }

    void add_conntecion(int city_a, int city_b, int weight){
            graph[city_a][city_b] = graph[city_b][city_a] = min(graph[city_a][city_b], (ll)weight);
    }

    void load_built_ways(){
        int city_a, city_b, weight;

        for (int i = 0; i < built_ways; i++){
            cin >> city_a >> city_b >> weight;
            add_conntecion(city_a, city_b, weight);
        }
    }

    void calculate_distances(){
        for (int k = 1; k <= number_of_cities; k++)
            for (int i = 1; i <= number_of_cities; i++)
                for(int j = 1; j <= number_of_cities; j++)
                    graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);
    }

    void update_distances(int city_a, int city_b, int weight){
        for(int i = 1; i <= number_of_cities; i++)
            for(int j = 1; j <= number_of_cities; j++) {
                graph[i][j] = min(graph[i][j], graph[i][city_a] + weight + graph[city_b][j]);
                graph[i][j] = min(graph[i][j], graph[i][city_b] + weight + graph[city_a][j]);
            }
    }

    bool is_shorter_path(ll prev_distance, ll new_distance){
        return new_distance < prev_distance;
    }

    bool is_better_way(int city_a, int city_b, int weight){
        return (min(graph[1][city_a] + graph[city_b][number_of_cities], graph[1][city_b] + graph[city_a][number_of_cities]) + weight)  < graph[1][number_of_cities];

    }

    void check_new_ways(){
        int city_a, city_b, weight;

        for (int i = 0; i < new_ways; i++){
            cin >> city_a >> city_b >> weight;

            if (is_better_way(city_a, city_b, weight)){
                cout << 1 << "\n";
                update_distances(city_a, city_b, weight);
            }
            else{
                cout << 0 << "\n";
            }
        }
    }
};

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
    Bitocja bitocja;
    bitocja.load_built_ways();
    bitocja.calculate_distances();
    bitocja.check_new_ways();
    return 0;
}

 

EDIT: znalazłem rozwiązanie podawane przez twórców https://oi.edu.pl/old/html/zadania/oig1/Etap3/bit.pdf
napisałem wszystko w funkcji main i tworząc dynamiczne tablice zamiast vectorów, nadal za wolno