Skip to content
The Chat Archive
o1-preview-2024-09-12· OpenAI WildChat-4.8M (AI2)

Azərbaycanca danış və This is the easy version of the problem. The difference between…

  1. User

    Azərbaycanca danış və This is the easy version of the problem. The difference between the versions is that in this version, there is an additional constraint on m . You can hack only if you solved all versions of this problem.

    Recently, the instructors of "T-generation" needed to create a training contest. They were missing one problem, and there was not a single problem on graphs in the contest, so they came up with the following problem.

    You are given a connected weighted undirected graph with n vertices and m edges, which does not contain self-loops or multiple edges.

    There are q queries of the form (a,b,k) : among all paths from vertex a to vertex b , find the smallest k -th maximum weight of edges on the path† .

    The instructors thought that the problem sounded very interesting, but there is one catch. They do not know how to solve it. Help them and solve the problem, as there are only a few hours left until the contest starts.

    † Let w1≥w2≥…≥wh be the weights of all edges in a path, in non-increasing order. The k -th maximum weight of the edges on this path is wk .

    Input Each test contains multiple test cases. The first line contains a single integer t (1≤t≤100 ) — the number of test cases. The description of the test cases follows.

    The first line of each set of test case contains three integers n,m and q (2≤n≤400 , n−1≤m≤min(400,n⋅(n−1)2) , 1≤q≤3⋅105 ) — the number of vertices, the number of edges, and the number of questions, respectively.

    Each of the following m lines of each set of test case contains three integers v,u and w (1≤v,u≤n , 1≤w≤109 ) — the ends of the next edge of the graph and its weight, respectively. It is guaranteed that the graph does not contain self-loops and multiple edges.

    Each of the following q lines of each set of test case contains three integers a,b and k (1≤a,b≤n , k≥1 ) — the next question. It is guaranteed that any path from vertex a to vertex b contains at least k edges.

    It is guaranteed that the sum of the values of n across all sets of test cases does not exceed 400 .

    It is guaranteed that the sum of the values of m across all sets of test cases does not exceed 400 .

    It is guaranteed that the sum of the values of q across all sets of test cases does not exceed 3⋅105 .

    Output For each test case, output the answers to all questions.

    Example InputCopy 3 4 4 2 1 2 2 2 4 2 1 3 4 3 4 1 1 4 2 2 3 1 6 7 3 1 2 10 2 3 3 3 4 9 4 5 2 5 6 1 2 4 10 4 6 10 1 6 3 1 6 2 2 4 1 11 17 10 1 4 5 1 3 19 1 2 10 3 2 13 4 5 1 4 6 11 3 5 9 3 6 18 2 7 17 5 8 15 5 10 8 6 9 4 7 10 20 7 8 16 8 11 3 9 11 6 10 11 14 3 11 1 3 11 3 1 11 1 1 11 4 1 11 3 8 2 2 10 4 1 3 9 2 3 9 1 6 7 3 OutputCopy 1 2 2 9 9 11 3 11 1 3 10 8 4 11 4 Note In the first set of test cases, one of the optimal paths in the first query is the path 1→3→4 ; the 2 -nd maximum weight of the edges on this path is 1 . In the second query, one of the optimal paths is 2→1→3 and 2→4→3 ; in both the 1 -st maximum weight of the edges is 2 .

    In the second set of input data, one of the optimal paths in the first query is the path 1→2→4→5→6 ; the 3 -rd maximum weight of the edges on this path is 2 . bu sualda nə deyilir onu mənə de və kodu c++da yaz

  2. Assistant

    Bu sualda birləşdirici, çəkili və istiqamətsiz qraf verilir. Sual budur ki, verilmiş (a) və (b) təpələri arasında olan bütün yollar arasında, k-tam maksimum kənar çəkisi ən kiçik olanı tapmaq lazımdır.

    Problem: Bizə (n) təpəsi və (m) kənarı olan bir qraf verilir. Hər bir kənarın çəkisi vardır. Hər bir sorğu üçün ((a), (b), (k)) təpələri arasında olan yollardan, k-tam maksimum kənar çəkisi ən kiçik olan yolu tapmaq lazımdır.

    Yanaşma: Qrafımız kiçik olduğundan ((n \leq 400)), lakin sorğuların sayı böyükdür ((q \leq 3 \times 10^5)), biz hər bir sorğu üçün effektiv bir metod istifadə etməliyik.

    Biz bu problemi həll etmək üçün qraf kənarlarının çəkilərini artan sıra ilə düzəldəcəyik və hər bir sorğu üçün kənar çəkiləri üzərində binar axtarış edəcəyik.

    Algoritm:

    1. Kənar çəkilərini toplamaq və sıralamaq:

      • Bütün unikal kənar çəkilərini topla və artan sıra ilə sıralamaq.
    2. Hər bir sorğu üçün binar axtarış:

      • Hər bir sorğu üçün, mümkün olan minimal k-tam maksimum kənar çəkisini tapmaq üçün kənar çəkiləri üzərində binar axtarış etmək.
      • Bunu edərkən, seçilmiş maksimum kənar çəkisi ilə qrafda (a) təpəsindən (b) təpəsinə ən az (k) uzunluğunda bir yolun olub-olmadığını yoxlamaq üçün BFS (Eninə axtarış) istifadə etmək.
    3. BFS tətbiqi:

      • Verilmiş maksimum kənar çəkisi ilə qrafı qur.
      • BFS istifadə edərək, (a) təpəsindən başlayıb (b) təpəsinə olan minimal yolu tap.
      • Əgər yolun uzunluğu (k) və ya daha böyükdürsə, onda bu çəkini cavab kimi qəbul et və binar axtarışı davam etdir.
    4. Nəticələri çıxarmaq:

      • Hər bir sorğu üçün tapılan minimal kənar çəkisini çıxar.

    Kod:

    #include <iostream>
    #include <vector>
    #include <algorithm>
    #include <queue>
    #include <map>
    #include <set>
    
    using namespace std;
    
    const int INF = 1e9;
    
    struct Edge {
        int u, v, w;
    };
    
    int n, m, q;
    
    vector<Edge> edges;
    vector<int> weights;
    map<int, vector<pair<int, int>>> weightToEdges;
    
    vector<int> adjList[405];
    
    bool bfs(int maxWeight, int a, int b, int k) {
        vector<int> dist(n+1, INF);
        queue<int> q;
        dist[a] = 0;
        q.push(a);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            if (dist[u] >= n) continue;
            for (int v : adjList[u]) {
                if (dist[v] > dist[u] + 1) {
                    dist[v] = dist[u] +1;
                    if (dist[v] >= n) continue;
                    q.push(v);
                }
            }
        }
        return dist[b] >= k;
    }
    
    int main() {
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
    
        int t;
        cin >> t;
        while (t--) {
            cin >> n >> m >> q;
            edges.clear();
            weights.clear();
            weightToEdges.clear();
            for (int i = 1; i <= n; ++i) {
                adjList[i].clear();
            }
    
            for (int i = 0; i < m; ++i) {
                int u, v, w;
                cin >> u >> v >> w;
                edges.push_back({u, v, w});
                weights.push_back(w);
                weightToEdges[w].push_back({u, v});
            }
    
            sort(weights.begin(), weights.end());
            weights.erase(unique(weights.begin(), weights.end()), weights.end());
    
            vector<tuple<int, int, int, int>> queries; // {index, a, b, k}
            for (int i = 0; i < q; ++i) {
                int a, b, k;
                cin >> a >> b >> k;
                queries.push_back({i, a, b, k});
            }
    
            vector<int> answers(q, -1);
    
            for (auto& query : queries) {
                int idx = get<0>(query);
                int a = get<1>(query);
                int b = get<2>(query);
                int k = get<3>(query);
    
                int left = 0, right = weights.size()-1;
                int ans = -1;
                while (left <= right) {
                    int mid = (left + right)/2;
                    int maxWeight = weights[mid];
    
                    // Build the graph with edges <= maxWeight
                    for (int i = 1; i <= n; ++i) {
                        adjList[i].clear();
                    }
                    for (auto& e : edges) {
                        if (e.w <= maxWeight) {
                            adjList[e.u].push_back(e.v);
                            adjList[e.v].push_back(e.u);
                        }
                    }
    
                    if (bfs(maxWeight, a, b, k)) {
                        ans = maxWeight;
                        right = mid -1;
                    } else {
                        left = mid +1;
                    }
                }
                answers[idx] = ans;
            }
    
            for (int i = 0; i < q; ++i) {
                cout << answers[i] << " ";
            }
            cout << "\n";
        }
    
        return 0;
    }
    

    İzah:

    • Proqram təkərli test halları üçün dövr etmir.
    • Hər bir test halı üçün, kənarları və onların çəkilərini oxuyur.
    • Kənar çəkilərini sıralayır və təkrarlananları silir.
    • Hər bir sorğu üçün, binar axtarış edərək minimal mümkün çəkini tapır.
    • Hər bir binar axtarış addımında, cari maksimum çəkidən kiçik və ya bərabər olan kənarlarla qrafı qurur və BFS ilə yolun uzunluğunu yoxlayır.
    • Nəticələri çap edir.

    Qeyd:

    • Bu həll hər bir sorğu üçün (O(\log M \times (N + M))) vaxtı sərf edir, burada (M) kənarların sayıdır.
    • Qrafın kiçik olmasına görə (maximum 400 təpə), həll praktikdir və vaxt limitindən keçəcəkdir.