fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std ; 
  3.  
  4.  
  5. #define ll long long 
  6. #define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  7. #define fir first 
  8. #define sec second 
  9. #define piint pair < int , int >
  10. #define FOR( i , a , b ) for (int i = (a) , _b = (b) ; i <= _b ; i ++ )  
  11. #define pb push_back 
  12. #define str string 
  13. #define ALL(a) (a).begin() , (a).end() 
  14. #define rep( i , a , b) for (int i = (a) ; i < (b) ; i ++ )
  15. #define ld long double
  16. const int maxn = 1e3;
  17. #define debug 0
  18. // #define oo (ll)(1e18)
  19.  
  20.  
  21.  
  22.  
  23. #define oo (ll)(1e15) 
  24. int n  ,  k ; 
  25. struct CRUISE
  26. {
  27. 	bool kind ;
  28. 	int u , v ;
  29. 	ll cost ;
  30. };
  31. CRUISE a[5*maxn+3];
  32. ll d[maxn+3][maxn+3] ;
  33. void input(){
  34. 	cin >> n >>  k ;
  35. 	FOR( i , 1 , n )
  36. 	FOR( j , 1 ,n ){
  37. 		if ( i == j ) d[i][j] = 0 ;
  38. 		else d[i][j]=oo ;
  39. 	}
  40. 	FOR ( i , 1 , k ){
  41. 		cin >> a[i].kind >> a[i].u >> a[i].v ;
  42. 		if (a[i].kind) { cin >> a[i].cost ; }
  43. 	}	
  44. }
  45.  
  46. void solve(){
  47.  
  48. 	FOR (i , 1 , k ){
  49. 		auto c = a[i] ;
  50. 		if (!a[i].kind){
  51. 			if (debug) cout << c.u << ' ' << c.v << '\n';
  52. 			if(d[c.u][c.v] == oo ) cout << -1 << '\n';
  53. 			else cout << d[c.u][c.v] << '\n'; 
  54. 		}
  55. 		else{
  56. 			d[a[i].u][a[i].v] = min ( a[i].cost , d[a[i].v][a[i].u] ) ;
  57. 			d[a[i].v][a[i].u] = min ( a[i].cost , d[a[i].u][a[i].v] ) ;
  58. 			FOR ( j , 1 , n ){
  59. 				FOR ( k , 1 , n ){
  60. 					if (d[j][c.u] != oo && d[c.v][k] != oo){
  61. 						d[j][k] = min ( d[j][k] , d[j][c.u] + d[c.v][k] + d[c.u][c.v]) ;
  62. 					}
  63. 				}
  64. 			}
  65. 		}
  66. 	}
  67. }
  68. #define name "CRUISE" 
  69. int main(){
  70.     fast 
  71.     if(fopen(name".INP","r")) {
  72.         freopen (name".INP","r",stdin);
  73.         freopen (name".OUT","w",stdout);
  74.     }
  75.     input() ;
  76.     solve() ;
  77.     cerr << "\nTIME: = " << (1.0*clock())/CLOCKS_PER_SEC << '\n';
  78.     return(0) ;
  79. }
Success #stdin #stdout #stderr 0.01s 5948KB
comments (?)
stdin
copy 
50 200
1 1 2 10
1 2 3 20
1 3 4 15
1 4 5 25
1 5 6 30
1 6 7 35
1 7 8 40
1 8 9 45
1 9 10 50
1 10 11 55
1 11 12 60
1 12 13 65
1 13 14 70
1 14 15 75
1 15 16 80
1 16 17 85
1 17 18 90
1 18 19 95
1 19 20 100
1 20 21 105
1 21 22 110
1 22 23 115
1 23 24 120
1 24 25 125
1 25 26 130
1 26 27 135
1 27 28 140
1 28 29 145
1 29 30 150
1 30 31 155
1 31 32 160
1 32 33 165
1 33 34 170
1 34 35 175
1 35 36 180
1 36 37 185
1 37 38 190
1 38 39 195
1 39 40 200
1 40 41 205
1 41 42 210
1 42 43 215
1 43 44 220
1 44 45 225
1 45 46 230
1 46 47 235
1 47 48 240
1 48 49 245
1 49 50 250
0 1 10
0 1 20
0 1 30
0 1 40
0 1 50
0 10 20
0 20 30
0 30 40
0 40 50
1 1 25 100
1 25 50 110
0 1 25
0 1 50
1 10 25 50
0 1 25
1 25 30 20
0 1 30
1 30 35 10
0 1 35
1 35 40 15
0 1 40
1 40 45 5
0 1 45
1 45 50 5
0 1 50
1 5 15 50
1 15 25 60
1 25 35 70
1 35 45 80
1 45 50 90
0 5 15
0 15 25
0 25 35
0 35 45
0 45 50
1 2 10 100
1 10 20 200
1 20 30 300
1 30 40 400
1 40 50 500
0 2 10
0 10 20
0 20 30
0 30 40
0 40 50
1 1 50 50
0 1 50
1 1 10 5
0 1 10
1 10 20 5
0 1 20
1 20 30 5
0 1 30
1 30 40 5
0 1 40
1 40 50 5
0 1 50
0 1 10
0 1 20
0 1 30
0 1 40
0 1 50
0 5 10
0 10 15
0 15 20
0 20 25
0 25 30
0 30 35
0 35 40
0 40 45
0 45 50
1 1 5 7
1 5 10 8
1 10 15 9
1 15 20 10
1 20 25 11
1 25 30 12
1 30 35 13
1 35 40 14
1 40 45 15
1 45 50 16
0 1 5
0 5 10
0 10 15
0 15 20
0 20 25
0 25 30
0 30 35
0 35 40
0 40 45
0 45 50
1 1 50 100
0 1 50
1 1 20 80
1 20 40 90
1 40 50 70
0 1 20
0 20 40
0 40 50
1 5 25 50
1 25 45 60
1 45 50 70
0 5 25
0 25 45
0 45 50
1 1 3 15
1 3 7 20
1 7 11 25
1 11 15 30
1 15 19 35
1 19 23 40
1 23 27 45
1 27 31 50
1 31 35 55
1 35 39 60
1 39 43 65
1 43 47 70
1 47 50 75
0 1 50
0 3 7
0 7 11
0 11 15
0 15 19
0 19 23
0 23 27
0 27 31
0 31 35
0 35 39
0 39 43
0 43 47
0 47 50


1 11 12 60
1 12 13 65
1 13 14 70
1 14 15 75
1 15 16 80
1 16 17 85
1 17 18 90
1 18 19 95
1 19 20 100
1 20 21 105
1 21 22 110
1 22 23 115
1 23 24 120
1 24 25 125
1 25 26 130
1 26 27 135
1 27 28 140
1 28 29 145
1 29 30 150
1 30 31 155
stdout
copy 
270
1045
2320
4095
6370
775
1275
1775
2275
100
210
100
120
130
145
150
155
50
60
70
80
5
100
200
300
140
155
50
5
10
15
20
25
5
10
15
20
25
160
325
115
25
20
10
15
5
5
7
8
9
10
11
12
10
14
5
5
50
65
65
5
50
60
5
25
20
25
30
35
40
45
50
55
60
65
70
75
stderr
copy 
TIME: = 0.005019
https://ideone.com/WCqsEe
language:
C++14 (gcc 8.3)
created:
6 days 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!