UVa/10048 - Audiophobia.cpp at master · justincsd/UVa · GitHub

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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
// Solved
#include<bits/stdc++.h>

using namespace std;

#define MM 101

struct edge{
    int u, v, w;
    bool operator<(const edge& p) const
    {
        return w < p.w;
    }
};

int pr[MM];
int dis[MM][MM];
int dir[MM];
vector<edge> e;
vector<int> g[MM];

int _find(int r)
{
    if(pr[r]==r) return r;
    return _find(pr[r]);
}
void kruskal(int n)
{
    sort(e.begin(), e.end());
    for (int i=1; i<=n; i++)
        pr[i]=i;

    int sz=e.size();
    int count=0;
    for (int i=0; i<sz; i++) {
        int u=_find(e[i].u);
        int v=_find(e[i].v);
        if (u != v){
            pr[u]=v;
            g[e[i].u].push_back(e[i].v);
            g[e[i].v].push_back(e[i].u);
            dis[e[i].u][e[i].v]=e[i].w;
            dis[e[i].v][e[i].u]=e[i].w;
            count++;
            if(count==n-1){
                break;
            }
        }
    }
}

void bfs(int s, int d)
{
    bool vis[MM];
    memset(vis, false, sizeof vis);
    vis[s]=true;
    queue<int> q;
    q.push(s);
    while(!q.empty()){
        int u=q.front();
        q.pop();

        for(int i=0; i<g[u].size(); i++){
            int v;
            v=g[u][i];
            if(!vis[v]){
                dir[v]=u;
                q.push(v);
                vis[v]=true;
                if(v==d){
                    return;
                }
            }
        }
    }
}
int main()
{
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    int t=1;
    while(1){

        e.clear();
        for(int i=0; i<MM; i++){
            g[i].clear();
        }
        int c, s, q;


        scanf("%d%d%d", &c, &s, &q);

        if(!c && !s && !q) break;
        if(t!=1) printf("\n");
        for(int i=0; i<s; i++){
            int u, v, w;
            scanf("%d%d%d", &u, &v, &w);

            edge get;
            get.u=u;
            get.v=v;
            get.w=w;
            e.push_back(get);
        }
        kruskal(c);
        printf("Case #%d\n", t++);

        for(int i=0; i<q; i++){
            int u, v;
            scanf("%d%d", &u, &v);
            bfs(u, v);
            if(_find(u)!=_find(v)){
                printf("no path\n");
            }
            else{
                int minMx=-1;
                while(u!=v){
                    //cout << u << " " << v << endl;
                    minMx=max(minMx, dis[v][dir[v]]);
                    v=dir[v];
                }
                printf("%d\n", minMx);
            }
        }
    }

    return 0;
}