Zadanie Grafowe Biotocja [OIG]

Mam takie zadanie Bitocja

Moje rozwiązanie z użyciem algorytmu Dijkstry:

#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;                                                               
    ll min_distance;                                                            
    vector<vector<pair<int, int>>> graph;                                       
public:                                                                                                                                                                                                                               
    void add_way(int city_a, int city_b, int weight){                           
        graph[city_a].push_back(make_pair(city_b, weight));                     
        graph[city_b].push_back(make_pair(city_a, weight));                     
    }                                                                           
                                                                               
    void delete_way(int city_a, int city_b){                                    
        graph[city_a].pop_back();                                               
        graph[city_b].pop_back();                                               
    }                                                                           
                                                                               
    Bitocja(){                                                                  
        int city_a, city_b, weight;                                             
                                                                                
        cin >> number_of_cities >> built_ways >> new_ways;                      
                                                                                
        graph.resize(number_of_cities + 1);                                     
                                                                                
        for (int i = 0; i < built_ways; i++){                                   
            cin >> city_a >> city_b >> weight;                                  
            add_way(city_a, city_b, weight);                                    
        }                                                                       
    }                                                                           
                                                                              
    ll calculate_min_dist_between_first_and_last(){                             
        priority_queue<pair<ll, ll>, vector<pair<ll, ll>> , greater<pair<ll, ll>>> pq;                                                                          
                                                                         
        vector<ll> dist(number_of_cities + 1, INF);                             
                                                                               
        pq.push(make_pair(0, 1));                                               
        dist[1] = 0;                                                            
                                                                               
        while (!pq.empty()){                                                    
            ll curr_vertex = pq.top().second;                                   
            pq.pop();     
                                                                                                               
            for (pair<ll, ll> next : graph[curr_vertex]){                       
                ll vertex = next.first;                                         
                ll weight = next.second;      

                if (dist[vertex] > dist[curr_vertex] + weight){                 
                    dist[vertex] = dist[curr_vertex] + weight;                  
                    pq.push(make_pair(dist[vertex], vertex));                   
                }                                                               
            }                                                                   
        }                                                                       
                                                                                
        return dist[number_of_cities];                                          
    }                                                                           
                                                                                
    bool is_good_way(ll distance){                                              
        return distance < min_distance;                                         
    }                                                                           
                                                                                
    void check_new_ways(){                                                      
        min_distance = calculate_min_dist_between_first_and_last();             
                                                                                
        int city_a, city_b, weight;                                             
                                                                                
        for (int i = 0; i < new_ways; i++){                                     
            cin >> city_a >> city_b >> weight;                                  
            add_way(city_a, city_b, weight);                                    
            ll new_distance = calculate_min_dist_between_first_and_last();      
            if (is_good_way(new_distance)){                                     
                cout << 1 << '\n';                                              
                min_distance = new_distance;                                    
            }                                                                   
            else{                                                               
                cout << 0 << '\n';                                              
                delete_way(city_a, city_b);                                     
            }                                                                   
        }                                                                       
    }                                                                           
};                                                                              
                                                                                
int main() {                                                                    
    ios_base::sync_with_stdio(0);                                               
    cin.tie(nullptr);                                                           
    Bitocja bitocja;                                                            
    bitocja.check_new_ways();                                                   
    return 0;                                                                   
}    

Niestety za wolne, czytałem gdzieś że trzeba użyć Floyda-Warhalla, tylko jak go później zmieniać wraz z zmianami w grafie ? I gdy zrobimy zmiane którą trzeba będzie cofnąć a utworzą już się nowe połączenia, trzeba kopiować macierz ?

Okej poprawiłem algorytm na Floyda-Warshalla nie trzeba było robić żadnego kopiowania grafu tylko sprawdzić czy nowa droga będzie dawała lepsze rozwiązanie, algorytm poprawił się czasowo ale jeszcze jest dla kilku testów 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;
}

Jak przyspieszyć mój algorytm?

EDIT: znalazłem rozwiązanie podawane przez twórców https://oi.edu.pl/old/html/zadania/oig1/Etap3/bit.pdf
nie wiem co mam zrobić żeby było szybciej

EDIT:napisałem wszystko w funkcji main i tworząc dynamiczne tablice zamiast vectorów, nadal za wolno

Wróć do wektorów, czyste tablice dynamiczne wcale Ci nie przyśpieszą a jedynie utrudnią temat.

Pytanie brzmi:
Jak duża jest liczba wierzchołków w tym grafie?
No, bo możliwe, że funkcja calculate_distances wszystko spowalnia ze względu na to, że ma w sobie aż 3 fory a istnieje możliwość rozłożyć pracę na kilka różnych wątków.