fork download
  1. // In the name the Allah the Most Merciful.
  2.  
  3. #include<bits/stdc++.h>
  4. using namespace std;
  5.  
  6. typedef long long ll;
  7. const int MAX = 10005;
  8. const ll INF = 1e18;
  9.  
  10. vector<pair<ll , ll > > edges[MAX+9];
  11. ll dis[MAX+9];
  12.  
  13. void Dijkstra(ll now)
  14. {
  15. priority_queue<pair<ll , ll > > pq;
  16. dis[now] = 0;
  17. pq.push(make_pair(0 , now));
  18. while(!pq.empty()){
  19.  
  20. ll u = pq.top().second;
  21. ll c1 = -pq.top().first;
  22. pq.pop();
  23.  
  24. if(c1>dis[u])continue;
  25.  
  26. for(auto t : edges[u]){
  27.  
  28. ll v = t.first;
  29. ll c = t.second;
  30.  
  31. if(dis[v]>dis[u]+c){
  32.  
  33. dis[v] = dis[u]+c;
  34. pq.push(make_pair(-dis[v] , v));
  35. }
  36. }
  37. }
  38. }
  39.  
  40. int main(void)
  41. {
  42. string ar;
  43. while(getline(cin , ar)){
  44.  
  45. if(ar==""){
  46.  
  47. for(int i=0;i<=MAX;i++)dis[i] = INF;
  48. Dijkstra(1);
  49.  
  50. ll next = -1 , mx = 0;
  51.  
  52. for(int i=1;i<=MAX;i++){
  53.  
  54. if(dis[i]!=INF){
  55.  
  56. if(mx<dis[i]){
  57.  
  58. mx = dis[i];
  59. next = i;
  60. }
  61. }
  62. }
  63.  
  64. for(int i=0;i<=MAX;i++)dis[i] = INF;
  65. Dijkstra(next);
  66.  
  67. mx = 0;
  68. for(int i=1;i<=MAX;i++){
  69.  
  70. if(dis[i]!=INF)mx = max(mx , dis[i]);
  71. }
  72.  
  73. cout << mx << endl;
  74. for(int i=0;i<MAX;i++)edges[i].clear();
  75. continue;
  76. }
  77.  
  78. stringstream ss(ar);
  79. ll in1 ,in2 , in3;
  80. ss >> in1;
  81. ss >> in2;
  82. ss >> in3;
  83.  
  84. edges[in1].push_back(make_pair(in2 , in3));
  85. edges[in2].push_back(make_pair(in1 , in3));
  86. }
  87.  
  88. for(int i=0;i<=MAX;i++)dis[i] = INF;
  89. Dijkstra(1);
  90.  
  91. ll next = -1 , mx = 0;
  92.  
  93. for(int i=1;i<=MAX;i++){
  94.  
  95. if(dis[i]!=INF){
  96.  
  97. if(mx<dis[i]){
  98.  
  99. mx = dis[i];
  100. next = i;
  101. }
  102. }
  103. }
  104.  
  105. for(int i=0;i<=MAX;i++)dis[i] = INF;
  106. Dijkstra(next);
  107.  
  108. mx = 0;
  109. for(int i=1;i<=MAX;i++){
  110.  
  111. if(dis[i]!=INF)mx = max(mx , dis[i]);
  112. }
  113.  
  114. cout << mx << endl;
  115. for(int i=0;i<MAX;i++)edges[i].clear();
  116.  
  117.  
  118. return 0;
  119. }
  120.  
Success #stdin #stdout 0s 15552KB
stdin
11 4 144
11 9 4233
4 3 2672
4 8 7405
9 6 7282
9 7 6270
3 1 7066
3 2 9363
3 10 5388
8 5 6771

5 4 4526
5 2 1670
4 3 8274
4 6 9711
4 1 6157

2 4 9141
2 1 9030
2 3 2030

5 3 1654
3 8 3937
8 6 2090
6 4 6752
4 1 4311
4 2 8422
4 7 1668

3 2 8227
2 6 2384
2 7 1126
6 1 8049
7 5 432
7 4 780

2 1 3184

7 4 7397
4 6 6109
4 3 3296
4 8 6094
6 5 3157
3 2 9774
3 9 8400
8 1 900

2 1 6716
1 3 1438

4 3 3246
4 2 9305
3 1 3509

6 2 2740
2 4 2721
4 7 6476
4 8 9292
4 1 212
7 3 2647
7 9 6928
8 5 4085

1 2 9229

5 1 1833
1 3 1843
3 8 6002
3 6 4583
3 4 505
8 2 5210
6 7 8015
4 9 7356

5 2 2004
2 3 519
2 1 6891
3 6 9009
3 4 2247

2 3 1125
2 1 799

9 3 9954
9 7 3257
9 2 3782
3 6 709
7 5 9749
7 8 6248
7 4 4914
2 1 6767

5 2 8897
2 6 1636
2 7 7656
6 4 3378
7 3 8997
7 1 6682

3 6 7015
3 7 7191
6 10 5172
6 1 8346
6 4 3406
7 2 211
7 9 4826
7 8 1449
10 5 75

2 1 1595

2 6 2746
6 7 2595
7 8 8440
7 5 754
8 4 1983
5 1 9738
4 3 5439

7 6 2833
7 8 5721
7 4 8133
6 5 1162
6 2 1359
6 1 1963
8 3 6763

2 11 6173
11 4 4162
11 10 2791
11 5 7747
4 3 5836
4 7 8984
10 1 2965
5 6 3835
5 8 1098
5 9 1595

2 7 7986
2 6 5556
7 3 8573
7 1 6290
7 9 5679
6 5 8815
6 8 310
3 4 7958

6 8 8103
6 4 3020
6 5 6718
8 9 8593
8 1 5628
8 7 1345
4 3 2484
4 2 7183

4 1 6730
4 5 5849
1 3 3085
5 2 6648

2 3 7066
2 1 8901

6 1 9242
1 2 234
1 4 7219
2 5 3769
2 3 9535

2 4 7815
2 3 3241
2 5 6591
4 1 9889

3 1 9327
3 6 7245
3 5 5679
1 4 6023
1 2 4567

2 3 4923
3 4 4955
3 1 1293

1 2 2606

1 2 5414

1 5 4138
1 3 66
1 8 3752
5 4 986
3 2 6944
3 6 2139
3 7 1169

5 7 8989
5 6 8893
7 3 755
6 8 2538
3 2 6028
3 1 9614
3 4 2548

3 1 420
3 2 3725

8 3 2114
8 4 7076
3 6 3663
4 2 1730
4 1 9004
6 7 7887
6 5 6112

6 1 5062
6 8 7167
6 2 5864
1 3 4925
1 4 1616
8 5 1175
8 7 4889

2 1 515

1 4 8913
4 3 8269
4 8 1080
3 2 5016
3 9 3219
8 5 8535
8 10 5435
2 6 9812
2 7 7051

2 1 8133
2 7 1163
2 3 2557
1 6 7050
1 4 9288
1 5 9500

1 2 5118
1 3 5998

2 6 4208
2 5 9406
2 8 2096
6 4 290
6 1 4748
5 3 1794
8 9 2475
8 7 704

1 2 430

7 10 1764
7 6 2936
10 2 5568
6 5 7954
2 8 7823
2 1 4596
2 4 8764
5 3 2742
8 9 7961
8 11 3446

8 2 8384
8 10 4960
8 7 8472
2 3 1442
2 1 6588
10 9 9990
10 5 2156
10 6 5262
7 4 2524

2 6 8213
2 5 6724
2 7 7576
6 1 8194
6 3 9725
6 4 6850

2 3 8894
2 1 6247
3 4 6689

6 1 2572
6 7 5155
6 5 4306
1 4 792
7 2 4697
7 3 5358

5 4 6418
4 6 9904
6 7 445
6 3 9174
6 1 4705
7 2 210

9 6 3494
9 3 93
9 7 1950
6 5 361
3 8 838
7 2 5277
5 4 1598
5 1 8388

4 1 2226
4 5 4029
1 2 9554
5 3 7968
5 6 748

1 2 8481
1 5 3864
1 4 8500
2 3 4439

2 1 5364

6 8 2583
6 7 6950
6 4 9985
8 2 192
8 1 4305
8 5 9238
7 3 2615

4 2 2042
4 3 9892
2 1 2833

1 2 9712
1 4 5106
1 3 4190

2 1 3146
2 3 1972
1 4 7452
1 5 1210
1 6 908

4 11 7430
4 3 766
4 2 1557
11 9 5872
11 7 5747
11 10 2308
3 5 6647
2 6 2408
9 8 5433
9 1 5554

5 4 5600
5 1 3078
5 6 6966
4 3 2420
4 2 4852

2 1 3179
2 4 1873
1 3 5279
1 5 4182

2 3 4760
2 1 10

6 1 6901
1 3 1521
1 5 9077
1 2 4564
3 7 1922
3 4 5512

7 2 876
2 4 5041
2 10 887
4 5 4608
4 9 7912
4 3 7597
10 6 5565
10 1 6663
10 8 4746

2 6 5581
2 9 6439
2 8 7595
6 7 4795
9 10 9848
9 3 5076
9 4 4771
8 5 6470
8 1 5658

9 10 8553
9 2 8143
10 7 4723
2 1 5780
2 6 4438
2 4 8857
7 3 7229
1 8 149
1 5 2024

1 5 8890
1 10 8146
1 7 46
5 8 6567
5 6 7738
5 3 8100
10 9 774
7 2 4441
7 11 6554
8 4 9650

1 2 7121

9 3 3858
9 7 1328
9 1 331
3 4 5826
3 2 377
3 6 8647
7 8 8115
7 5 6748

9 6 5889
9 2 9599
9 5 8210
6 7 2272
2 1 7520
2 3 7571
2 4 5641
5 8 6576

3 2 3823
2 1 9951

2 1 8727

6 1 2504
1 7 3198
1 8 8216
7 5 8384
7 3 2089
7 4 8334
8 2 8758

3 4 6930
3 1 1806
3 2 3835

2 1 929

8 7 3870
8 4 5403
7 3 8438
7 6 2518
4 1 527
3 2 8543
3 5 9285

4 1 5730
1 6 4312
6 5 5415
6 8 9063
5 9 659
5 7 428
5 2 2876
8 3 650

3 1 6134
3 2 5968

5 2 9673
5 7 6955
5 1 8709
2 6 8012
2 4 792
7 3 2324

5 3 7575
5 2 3321
5 4 5170
3 1 1290

5 9 1857
5 11 3758
9 6 3055
9 10 1770
9 3 5381
11 4 446
11 2 7764
11 8 1181
6 7 2464
10 1 9058

3 2 927
3 1 4840

1 2 2212
1 3 3254

2 3 6746
2 7 1372
3 1 3545
3 6 5488
7 4 4435
7 5 7952
1 8 3493

2 3 1486
2 4 3796
3 7 5902
4 1 1730
4 6 7120
4 5 3424
7 8 2097

5 3 9527
3 2 7212
3 4 9372
3 7 1276
2 1 3446
2 6 3274

4 2 5424
2 1 2374
1 3 6122
3 5 7223

1 4 3778
1 2 9888
4 3 6406

1 8 5540
1 10 94
1 6 5700
8 7 8134
8 2 4426
8 11 1116
10 9 272
6 5 8461
6 4 8216
6 3 7682

3 8 4453
8 10 5472
10 6 6103
10 2 4700
10 4 258
6 1 6752
2 5 684
2 11 1178
4 7 1293
4 9 1450

8 7 2153
7 1 7009
7 3 6064
1 2 7838
1 6 7294
1 4 413
3 5 2766

2 1 1740

6 3 7741
3 4 9622
4 7 2942
7 2 5843
7 5 6254
7 8 6061
2 1 3264

5 3 6512
3 7 6220
3 4 9818
7 2 8239
7 6 160
7 1 7377

1 5 3741
1 3 6679
5 8 9802
5 2 599
5 6 7662
3 4 6831
8 7 4051

4 1 655
1 9 5509
1 7 3935
9 5 1397
7 2 6817
7 3 2233
5 10 558
5 8 5264
2 6 6713

2 1 4337
2 6 3183
1 4 1986
6 5 6266
6 3 5264
6 7 6127

1 2 1841

6 5 3440
5 3 3030
3 4 4585
3 2 4375
4 1 2690
2 7 9930

1 2 8556
1 10 7875
2 6 1145
10 9 1533
10 7 552
10 4 1994
6 8 6869
6 5 5434
6 3 3050

2 3 8496
3 1 6749

8 7 5463
7 3 5390
7 2 8004
3 5 9208
2 10 9683
2 9 1203
5 4 2904
5 6 2989
10 1 9155
stdout
26211
17985
18171
22855
18660
3184
22336
8154
16060
26781
9229
23810
16419
1924
23669
25550
27378
1595
26354
20617
24728
38888
26899
22312
15967
19011
24295
22595
9878
2606
5414
12134
30789
4145
29744
22043
515
32712
20190
11116
20156
430
36748
29922
25514
21830
14819
25496
19470
23777
21420
5364
21806
14767
14818
12570
26269
17418
10331
4770
16110
20503
30352
37505
34027
7121
21948
31956
13774
8727
28556
10765
929
27523
19755
12102
26964
14035
24207
5767
5466
23108
20401
20185
21143
20072
27835
22780
23677
1740
29412
24277
31104
29635
15772
1841
21580
26439
15245
44429