fork download 
  1. #include <cstring>
  2. #include <cmath>
  3. #include <algorithm>
  4. #include <cstdlib>
  5. #include <cstdio>
  6. #include <iostream>
  7. #include <fstream>
  8. #include <queue>
  9.  
  10. #define rep(i, l, r) for(int i = l; i <= r; i++)
  11. #define down(i, l, r) for(int i = l; i >= r; i--)
  12. #define MS 1234
  13. #define MAX 1037471823
  14. #define Q 12345678
  15.  
  16. using namespace std;
  17.  
  18. struct node
  19. {
  20. 	int x, y, z;
  21. 	bool operator < (const node &k) const { return z < k.z; }
  22. } c[5678];
  23. int n, m, s, t, ss, tt, h[567], v[34567];
  24. long long fz, fm;
  25.  
  26. int Head(int x) { while (h[h[x]] != h[x]) h[x] = h[h[x]]; return h[x]; }
  27.  
  28. int gcd(int x, int y) { return y==0 ? x : x<y ? gcd(x, y%x) : gcd(y, x%y); }
  29.  
  30. int main()
  31. {
  32. 	scanf("%d%d", &n, &m);
  33. 	fm = 1; fz = 123456;
  34. 	rep(i, 1, m) scanf("%d%d%d", &c[i].x, &c[i].y, &c[i].z); sort(c+1, c+1+m); c[m+1].z = MAX;
  35. 	v[1] = 1; rep(i, 2, 30000) { v[i] = v[i+1]; while (c[v[i]].z < i) v[i]++; }
  36. 	scanf("%d%d", &s, &t); ss = 1; 
  37. 	while (true)
  38. 	{
  39. 		rep(i, 1, n) h[i] = i;
  40. 		while (Head(s) != Head(t) && ss <= 30000) 
  41. 		{ 
  42. 			rep(i, v[ss], v[ss+1]-1) if (Head(c[i].x) != Head(c[i].y)) h[h[c[i].x]] = h[c[i].y];
  43. 			ss++;
  44. 		}
  45. 		if (ss > 30000) break; ss--;
  46. 		tt = ss;
  47. 		rep(i, 1, n) h[i] = i;
  48. 		while (Head(s) != Head(t)) 
  49. 		{ 
  50. 			rep(i, v[tt], v[tt+1]-1) if (Head(c[i].x) != Head(c[i].y)) h[h[c[i].x]] = h[c[i].y];
  51. 			tt--;
  52. 		}
  53. 		tt++; if (fm*ss < fz*tt) fz = ss, fm = tt; ss = tt+1;
  54. 	}
  55. 	n = gcd(fz, fm);
  56. 	if (fz == 123456) printf("IMPOSSIBLE\n"); else if (fz % fm == 0) printf("%lld\n", fz/fm); else printf("%lld/%lld\n", fz/n, fm/n);
  57. 	return 0;
  58. }
Success #stdin #stdout 0s 3508KB
comments (?)
stdin 
3 3
1 2 10
1 2 5
2 3 8
1 3
stdout 
5/4
https://ideone.com/sDZLNM
BZOJ 1050
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!