Cod sursa(job #1201646)

Utilizator dariusdariusMarian Darius dariusdarius Data 25 iunie 2014 17:00:13
Problema PScNv Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.14 kb
#include <algorithm>
#include <fstream>
#include <vector>
using namespace std;
const int MAX_K = 1005;
const int MAX_N = 250005;
const int BUFFER_SIZE = 1 << 16;

vector< pair<int, int> > edges[MAX_K];
int father[MAX_N];
int height[MAX_N];

inline int get_root(int x) {
    return x == father[x] ? x : (father[x] = get_root(father[x]));
}
inline bool united(int x, int y) {
    return get_root(x) == get_root(y);
}
inline void unite(int x, int y) {
    x = get_root(x); y = get_root(y);
    if(height[x] == height[y]) {
        ++ height[x];
        father[y] = x;
    } else if(height[x] < height[y]) {
        father[x] = y;
    } else {
        father[y] = x;
    }
}

class InputReader {
    public:
        InputReader() {}
        InputReader(const char* filename) {
            file = fopen(filename, "r");
            cursor = 0;
            fread(buffer, BUFFER_SIZE, 1, file);
        }
        inline InputReader & operator >> (int &n) {
            n = 0;
            while(!isdigit(buffer[cursor])) {
                advance();
            }
            while(isdigit(buffer[cursor])) {
                n = n * 10 + buffer[cursor] - '0';
                advance();
            }
            return *this;
        }
    private:
        int cursor;
        char buffer[BUFFER_SIZE];
        FILE* file;
        inline void advance() {
            ++ cursor;
            if(cursor == BUFFER_SIZE) {
                cursor = 0;
                fread(buffer, BUFFER_SIZE, 1, file);
            }
        }
};

int main() {
    InputReader fin("pscnv.in");
    ofstream fout("pscnv.out");
    int n, m, x, y, k;
    fin >> n >> m >> x >> y;
    for(int i = 1; i <= n; ++ i) {
        father[i] = i;
        height[i] = 1;
    }
    for(int i = 1; i <= m; ++ i) {
        int a, b, cost;
        fin >> a >> b >> cost;
        edges[cost].push_back(make_pair(a, b));
    }
    for(k = 1; !united(x, y); ++ k) {
        for(vector< pair<int, int> > :: iterator it = edges[k].begin(); it != edges[k].end(); ++ it) {
            if(!united(it->first, it->second)) {
                unite(it->first, it->second);
            }
        }
    }
    fout << k - 1 << "\n";
    return 0;
}