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
#include <bits/stdc++.h>
using namespace std;
int n,m,q,i,j,jj,c,a,b;
long long d,z,zz,kk;
array<long long,200001> k;
vector<array<long long,2>> f;
array<long long,200001> g;
array<vector<array<long long,2>>,200001> v;
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m >> q;
	for (i=0;i<m;i++){
		cin >> a >> b >> d;
		v[a].push_back({b,d});
		v[b].push_back({a,d});
	}
	for(i=0;i<q;i++)
	{
		//cout <<i << '\n';
		//if(i==2) return 0;
		cin >> c;
		if(c==1) {
			cin >> a >> b >> d;
			v[a].push_back({b,d});
			v[b].push_back({a,d});
			
		}
		else if(c==2){
			cin >> a >> b;
			v[a].push_back({b,0});
			v[b].push_back({a,0});
		}
		else if(c==3) {
			cin >> d >> z >> kk;
			f={{d,0}};
			j=0;
			k[d]=kk;
			g[d]=2;
			while(j<f.size()) {
				zz=f[j][0];
				for(auto d:v[zz])
					if(g[d[0]]>1)
						continue;
					else if(d[1]>0)
						g[d[0]]=1;
					else
						g[d[0]]=0;
				if(v[zz].size()>0)
					for(jj=v[zz].size()-1;jj>=0;jj--)
						if(g[v[zz][jj][0]]==1) {
							if(v[zz][jj][1]+f[j][1]<=z) {
								k[v[zz][jj][0]]=kk;
								f.push_back({v[zz][jj][0],v[zz][jj][1]+f[j][1]});
								g[v[zz][jj][0]]=2;
							}
							else
								g[v[zz][jj][0]]=0;
							
						}
				j++;
						
			}
			for(auto xx:f)
				g[xx[0]]=0;
			
		}
		else {
			cin >> d;
			
			cout << k[d] << '\n';
		}
	}
}