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
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <map>
int n,m,q,a,b,t,k,v,u;
long long d,z;
int kolors[200001];
std::vector<std::vector<std::pair<int,long long>>> sa;
void dfs(int wie,int oj,long long dist,int kol){
    kolors[wie]=k;
    for(auto x:sa[wie])
        if(x.first!=oj&&dist>=x.second)
            dfs(x.first,wie,dist-x.second,kol);
}
int main() {
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(NULL);
    std::cin>>n>>m>>q;
    sa.resize(n+1);
    for(int i=1;i<=n;i++)
        kolors[i]=0;
    for(int i=0;i<m;i++){
        std::cin>>a>>b>>d;
        sa[a].emplace_back(b,d);
        sa[b].emplace_back(a,d);
    }
    for(int i=0;i<q;i++){
        std::cin>>t;
        if(t==1){
            std::cin>>a>>b>>d;
            sa[a].emplace_back(b,d);
            sa[b].emplace_back(a,d);
        }
        if(t==2){
            std::cin>>a>>b;
            int i=0;
            while (sa[a][i].first!=b)
                i++;
            sa[a][i]=sa[a].back();
            sa[a].pop_back();
            i=0;
            while (sa[b][i].first!=a)
                i++;
            sa[b][i]=sa[b].back();
            sa[b].pop_back();
        }
        if(t==3){
            std::cin>>v>>z>>k;
            kolors[v]=k;
            for(auto x:sa[v])
                if(z>=x.second)
                    dfs(x.first,v,z-x.second,k);
        }
        if(t==4){
            std::cin>>v;
            std::cout<<kolors[v]<<"\n";
        }
        
    }
}