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 <bits/stdc++.h>
using namespace std;
using ll = long long;
#define FOR(i,a,b) for(ll i=a; i<=b; ++i)
#define pb push_back

constexpr int MAX_N=1e4+14, MAX_Q=2e5+14;//!! too small MAX_N
ll N, M, qtQ, dis[MAX_N][MAX_N], col[MAX_N];
vector<ll> edg[MAX_N];
void Input(){
    ll a,b,c;
    FOR(i,0,MAX_N-1) FOR(j,0,MAX_N-1) dis[i][j]=-1;
    cin>>N>>M>>qtQ;
    FOR(i,0,M-1){
        cin>>a>>b>>c;
        edg[a].pb(b);
        edg[b].pb(a);
        dis[a][b]=c;
        dis[b][a]=c;
    }

}
void DFS(ll cV, ll rDis, ll cCol, ll par){
    col[cV]=cCol;
    for(auto nV:edg[cV]){
        if(nV==par||dis[cV][nV]<=0||dis[cV][nV]>rDis) continue; 
        DFS(nV, rDis-dis[cV][nV], cCol, cV);
    }
}
void Solve(){
    ll a, b, c, d;
    FOR(qq,0,qtQ-1){
        cin>>a;
        if(a==1){   //adding
            cin>>b>>c>>d;
            if(dis[b][c]==-1){
                edg[b].pb(c);
                edg[c].pb(b);
            }
            dis[b][c]=d;
            dis[c][b]=d;
        }else if(a==2){//remove
            cin>>b>>c;
            dis[b][c]=-2;
            dis[c][b]=-2;
        }else if(a==3){//coloring
            cin>>b>>c>>d;
            DFS(b,c,d,-1);
        }else{          //printing
            cin>>a;
            cout<<col[a]<<"\n";
        }
    }
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    Input();
    Solve();
}