fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #define SIZE 1000
  4. #define INF 1000
  5. using namespace std;
  6. vector<pair<int,int>>G[SIZE];
  7. int dp[SIZE][SIZE];
  8. bool checker_place[SIZE][SIZE];
  9. int number_of_vertex,number_of_edge,number_of_new_way;
  10. void floydWarshall(int n){
  11. 	for(int i=1;i<=n;i++){
  12. 		for(int j=1;j<=n;j++){
  13. 			if(!checker_place[i][j]){
  14. 				dp[i][j]=INF;
  15. 			}
  16. 		}
  17. 	}
  18. 	for(int k=1;k<=n;k++){
  19. 		for(int i=1;i<=n;i++){
  20. 			for(int j=1;j<=n;j++){
  21. 				dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
  22. 			}
  23. 		}
  24. 	}
  25. }
  26. void addToGraph(int x,int y,int z){
  27. 	G[x].push_back({y,z});
  28. 	G[y].push_back({x,z});
  29. 	dp[x][y]=z;
  30. 	dp[y][x]=z;
  31. 	//changeDp
  32. 	for(int i=1;i<=number_of_vertex;i++){
  33. 		for(int j=1;j<=number_of_vertex;j++){
  34. 			dp[i][j]=min(dp[i][j],dp[i][x]+dp[x][y]+dp[y][j]);
  35. 		}
  36. 	}
  37. }
  38. int currentFloyd(int x,int y,int z){
  39. 	//1->(x-y)->n
  40. 	int result=0;
  41. 	result+=dp[1][x];
  42. 	result+=z;
  43. 	result+=dp[y][number_of_vertex];
  44. 	return result;
  45. }
  46. void checkNewWay(int x,int y,int z){
  47. 	int current_dist=dp[1][number_of_vertex];
  48. 	int new_distance=currentFloyd(x,y,z);
  49. 	if(new_distance<=current_dist){
  50. 		cout<<"1"<<endl;
  51. 		addToGraph(x,y,z);
  52. 	}else{
  53. 		new_distance= currentFloyd(y,x,z);
  54. 		if(new_distance<=current_dist){
  55. 			cout<<1<<endl;
  56. 			addToGraph(y,x,z);
  57. 		}else{
  58. 			cout<<"0"<<endl;
  59. 		}
  60. 	}
  61. }
  62. int main(){
  63. 	cin>>number_of_vertex>>number_of_edge>>number_of_new_way;
  64. 	for(int i=0;i<number_of_edge;i++){
  65. 		int x,y,z;
  66. 		cin>>x>>y>>z;
  67. 		G[x].push_back({y,z});
  68. 		G[y].push_back({x,z});
  69. 		dp[x][y]=z;
  70. 		dp[y][x]=z;
  71. 		checker_place[x][y]=true;
  72. 		checker_place[y][x]=true;
  73. 	}
  74. 	floydWarshall(number_of_vertex);
  75. 	for(int i=0;i<number_of_new_way;i++){
  76. 		int x,y,z;
  77. 		cin>>x>>y>>z;
  78. 		checkNewWay(x,y,z);
  79. 	}
  80. 	return 0;
  81. }
  82.  
Success #stdin #stdout 0.01s 5504KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/KuJYFm
language:
C++ (gcc 8.3)
created:
2 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!