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
#include <cstdio>
#include <map>
#include <vector>
#define DEBUG false
using namespace std;

struct Wierzcholek{
    int kolor;
    int nr;     // nr kolejnego malowania
    map<int, int> krawedz;
}V;

map<int, int>::iterator it;
vector<Wierzcholek> v;
int n,m,q,a,b,dlg,quest,kol,Nr=0;
long long z;

//drukuj liste wierzcholkow
void listaV(int a){
    printf("-- Wierzcholek %d --\n",a);
    for( it=v[a].krawedz.begin(); it!=v[a].krawedz.end(); it++)
        printf("do %d odleglosc:%d\n",it->first,it->second);
    return;
}

void maluj(int a, long long restDlg){

    //sprawdz czy juz odwiedzono ta krawedz podczas "nr" malowania
    if( v[a].nr == Nr)
        return;
    //printf("%d ",a);
    v[a].kolor = kol;
    v[a].nr = Nr;
    map<int, int>::iterator it;
    for( it = v[a].krawedz.begin(); it!=v[a].krawedz.end(); it++){
        if( (it->second <= restDlg )&& (v[it->first].nr != Nr) )
            maluj( it->first, restDlg - it->second );
    }
    return;
}

int main(){

    scanf(" %d %d %d",&n,&m,&q);
    V.kolor = 0; V.nr = 0;
    for(int i=0; i<=n; i++)
        v.push_back(V);
    for(int i=0; i<m; i++){
        scanf(" %d %d %d",&a,&b,&dlg);
        v[a].krawedz[b] = dlg;
        v[b].krawedz[a] = dlg;
    }

    if(DEBUG)listaV(1);
    if(DEBUG)listaV(2);
    for(int i=0; i<q; i++){
        scanf(" %d",&quest);
        switch(quest){
            //dodaj krawedz miedzy wierzcholkami a i b o dlugosci dlg
            case 1:
                scanf(" %d %d %d",&a,&b,&dlg);
                v[a].krawedz[b] = dlg;
                v[b].krawedz[a] = dlg;
                break;

            //usun krawedz miedzy wierzcholkami a i b
            case 2:
                scanf(" %d %d",&a,&b);
                v[a].krawedz.erase(b);
                v[b].krawedz.erase(a);
                break;

            //maluj od wierzcholka a kolorem kol oddalone maks o dlugosc z
            case 3:
                ++Nr;//numer malowania
                scanf(" %d %lld %d",&a,&z,&kol);
                maluj(a,z);
                break;

            //wypisz kolor wierzcholka
            case 4:
                scanf(" %d",&a);
                printf("%d\n",v[a].kolor);
                break;
        }
    }
    if(DEBUG)listaV(1);
    if(DEBUG)listaV(2);
    return 0;
}