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
#include <bits/stdc++.h>
#define MAX_N 200007
#define f first
#define s second
using namespace std;

vector<pair<int, long long>> graf[MAX_N];
int color[MAX_N];
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> q;
int odw[MAX_N];

void Astar(long long od, int k){
	int w;
	long long d;
	while(!q.empty()){
		while(!q.empty() && odw[q.top().s] == k) q.pop();
		if(q.empty()) break;
		w = q.top().s;
		d = q.top().f;
		q.pop();
		odw[w] = k;
		color[w] = k;
		for(auto& i : graf[w]){
			if(odw[i.f] != k){
				if(d + i.s <= od){
					q.push({d + i.s, i.f});
				}
			}
		}
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n, m, q1, a, b, z;
	long long c;
	cin >> n >> m >> q1;
	for(int i = 0; i < m; i++){
		cin >> a >> b >> c;
		graf[a].push_back({b, c});
		graf[b].push_back({a, c});
	}
	for(int Q = 0; Q < q1; Q++){
		cin >> z;
		switch(z){
			case 1:
				cin >> a >> b >> c;
				graf[a].push_back({b, c});
				graf[b].push_back({a, c});
				break;
			case 2:
				cin >> a >> b;
				for(int i = 0; i < (int)graf[a].size(); i++){
					if(graf[a][i].f == b){
						graf[a].erase(graf[a].begin()+i, graf[a].begin()+i+1);
					}
				}
				for(int i = 0; i < (int)graf[b].size(); i++){
					if(graf[b][i].f == a){
						graf[b].erase(graf[b].begin()+i, graf[b].begin()+i+1);
					}
				}
				break;
			case 3:
				cin >> a >> c >> b;
				q.push({0LL, a});
				Astar(c, b);
				break;
			case 4:
				cin >> a;
				cout << color[a] << '\n';
				break;
		}
	}
	return 0;
}