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
115
116
117
118
119
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

vector<long long int> cost;
vector<int> poprzednik;
void magicBFS(int node, long long int dist, int color, vector<int>& colors, vector<vector<pair<int, int>>>& edges)
{
    queue<int> kolejka;
    kolejka.push(node);
    cost[node] = 0;
    poprzednik[node] = 0;
    int total;
    while (!kolejka.empty())
    {
        int top = kolejka.front();
        colors[top] = color;
        kolejka.pop();
        for (auto& edge : edges[top])
        {
            if (poprzednik[top] == edge.first)
            {
                poprzednik[top] = 0;
                continue;
            }
            total = cost[top] + (long long int)edge.second;
            if (total <= dist)
            {
                kolejka.push(edge.first);
                cost[edge.first] = total;
                poprzednik[edge.first] = top;
            }
        }
    }
}
int main()
{
    
    int m, n, q;
    //wierz, kraw, quest
    cin >> n >> m >> q;
    vector<int> color(n+1, 0);
    vector<vector<pair<int, int>>> edges(n+1, vector<pair<int, int>>());   
    poprzednik = vector<int>(n + 1);
    cost = vector<long long int>(n + 1);
    int arg = 0;
    int arg1, arg2;
    long long int d;
    for (int i = 0; i < m; ++i)
    {
        cin >> arg1 >> arg2 >> d;
        edges[arg1].push_back(pair<int, int>(arg2, d));
        edges[arg2].push_back(pair<int, int>(arg1, d));

    }
    //cout << "oryginal: ";
    //printvec(edges);
    //cout << "\n";
    for (int i = 0; i < q; ++i)
    {
        cin >> arg;
        switch (arg)
        {
            case 1:
            {
                //ok
                cin >> arg1 >> arg2 >> d;
                //connect a1 a2 w/w a3
                edges[arg1].push_back(pair<int, int>(arg2, d));
                edges[arg2].push_back(pair<int, int>(arg1, d));
                break;
            }
            case 2:
            {
                //ok
                cin >> arg1 >> arg2;
                //delete arg1 arg2
              
                for (int i = 0; i < edges[arg1].size(); ++i)
                {
                    if (edges[arg1][i].first == arg2)
                    {
                        edges[arg1].erase(edges[arg1].begin(), edges[arg1].begin() + i + 1);
                        goto exit;
                    }
                }
                exit:
                for (int i = 0; i < edges[arg1].size(); ++i)
                {
                    if (edges[arg2][i].first == arg1)
                    {
                        edges[arg2].erase(edges[arg2].begin(), edges[arg2].begin()+i + 1);
                        break;
                    }
                }
                break;
            }
            case 3:
            {
                //?
                cin >> arg1 >> d >> arg2;
                //change color from arg 1 in range of d to arg2
                //TODO: implement bfs
                magicBFS(arg1, d, arg2, color, edges);
                break;
            }
            case 4:
            {
                //ok
                cin >> arg1;
                cout << color[arg1] << "\n";
                break;
            }
        }
       
    }

}