1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
/* 2024
 * Maciej Szeptuch
 */
#include <cstdio>
#include <queue>
#include <tuple>
#include <vector>

const int MAX_VERTS = 200001;

int verts;
int edges;
int queries;
int color[MAX_VERTS];

std::vector<std::pair<int, int>> graph[MAX_VERTS];

void color_verts(int start, long long int max_cost, int new_color);

int main(void)
{
    scanf("%d %d %d\n", &verts, &edges, &queries);
    for(int e = 0; e < edges; ++e)
    {
        int v1;
        int v2;
        int cost;
        scanf("%d %d %d", &v1, &v2, &cost);
        --v1;
        --v2;
        graph[v1].push_back({v2, cost});
        graph[v2].push_back({v1, cost});
    }

    for(int q = 0; q < queries; ++q)
    {
        int operation;
        int new_color;
        long long int max_cost;
        int v1;
        int v2;
        int cost;
        scanf("%d", &operation);
        switch(operation)
        {
        case 1:
            scanf("%d %d %d", &v1, &v2, &cost);
            --v1;
            --v2;
            graph[v1].push_back({v2, cost});
            graph[v2].push_back({v1, cost});
            break;

        case 2:
            scanf("%d %d", &v1, &v2);
            --v1;
            --v2;
            for(size_t n = 0; n < graph[v1].size(); ++n)
                if(graph[v1][n].first == v2)
                {
                    graph[v1][n] = graph[v1].back();
                    graph[v1].pop_back();
                    break;
                }

            for(size_t n = 0; n < graph[v2].size(); ++n)
                if(graph[v2][n].first == v1)
                {
                    graph[v2][n] = graph[v2].back();
                    graph[v2].pop_back();
                    break;
                }

            break;

        case 3:
            scanf("%d %lld %d", &v1, &max_cost, &new_color);
            --v1;
            color_verts(v1, max_cost, new_color);
            break;

        case 4:
            scanf("%d", &v1);
            printf("%d\n", color[v1 - 1]);
            break;
        }
    }

    return 0;
}

inline void color_verts(int start, long long int max_cost, int new_color)
{
    std::queue<std::tuple<int, long long int, int>> que;
    que.push({start, 0llu, -1});

    while(!que.empty())
    {
        auto [v, current_cost, parent] = que.front();
        que.pop();

        color[v] = new_color;
        for(auto &[n, edge_cost]: graph[v])
        {
            if(n == parent)
                continue;

            if(current_cost + edge_cost > max_cost)
                continue;

            que.push({n, current_cost + edge_cost, v});
        }
    }
}