Pagini recente » Cod sursa (job #318434) | Cod sursa (job #2308037) | Cod sursa (job #66387) | Cod sursa (job #2725826) | Cod sursa (job #1457073)
#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;
}