fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define N 100005
  3. #define A first
  4. #define B second
  5. #define MAX 1000000005
  6. using namespace std;
  7.  
  8. typedef pair<int, int> ii;
  9. typedef vector<ii> vii;
  10.  
  11. vii adjList[N];
  12. priority_queue<ii,vii, greater<ii> > Q;
  13. int dist[N];
  14.  
  15. bool checkpoint[N], finish[N], visited[N];
  16.  
  17. void run_djikstras(){
  18.  
  19. 	int u=0, v=0, w=0;
  20.  
  21. 	memset(visited,false,sizeof visited);
  22. 	for(int i=0;i<N;i++)	dist[i]=MAX;
  23.  
  24. 	Q.push(make_pair(0,0));
  25. 	while(!Q.empty()){
  26. 		u=Q.top().B;
  27. 		w=Q.top().A;
  28. 		Q.pop();
  29. 		visited[u]=true;
  30. 		if(dist[u]>w)	dist[u]=w;
  31. 		for(int i=0;i<(int)adjList[u].size();i++){
  32. 			v=adjList[u][i].B;
  33. 			if(dist[v]>dist[u]+adjList[u][i].A)	dist[v]=dist[u]+adjList[u][i].A;
  34. 			if(!visited[v]){
  35. 				visited[v]=true;
  36. 				Q.push(make_pair(dist[v],v));
  37. 			}
  38. 		}
  39. 	}
  40. }
  41.  
  42. int main(){
  43.  
  44. 	//cout<<MAX<<endl;
  45.  
  46. 	memset(checkpoint, false, sizeof(checkpoint));
  47. 	memset(finish, false, sizeof(finish));
  48.  
  49. 	int n, m, c, f, temp, u, v, w;
  50. 	cin>>n>>m>>c>>f;
  51.  
  52. 	for(int i=0;i<c;i++){
  53. 		cin>>temp;
  54. 		checkpoint[temp]=true;
  55. 	}
  56.  
  57. 	for(int i=0;i<f;i++){
  58. 		cin>>temp;
  59. 		finish[temp]=true;
  60. 	}
  61.  
  62.  
  63. 	for(int i=0;i<m;i++){
  64. 		cin>>u>>v>>w;
  65. 		adjList[u].push_back(make_pair(w, v));
  66. 	}
  67.  
  68. 	run_djikstras();	//gets all the shortest distances in the array dist[]
  69.  
  70. 	int ans=MAX, best=MAX; 
  71.  
  72. 	for(int i=0;i<=n;i++)
  73. 		if(finish[i])	best = min(best, dist[i]);	//best is the shortest distance from 0 to a finish node directly connected to it.
  74.  
  75. 	for(int i=0;i<=n;i++){
  76. 		if(checkpoint[i]){
  77. 			for(int j=0;j<(int)adjList[i].size();j++){
  78. 				if(adjList[i][j].B==0)	ans = min(ans, dist[i] + best);	//if 0 is connected
  79. 				if(finish[adjList[i][j].B])	ans = min(ans, dist[i] + adjList[i][j].A);	//if a finishing point is connected
  80. 			}
  81. 		}
  82. 	}
  83.  
  84. 	if(ans==MAX)	cout<<"-1"<<endl;
  85. 	else cout<<ans<<endl;
  86.  
  87. 	//system("pause");
  88. 	return 0;
  89. }
Success #stdin #stdout 0s 5336KB
comments (?)
stdin
copy 
5 12 2 2
1 3
2 4
0 1 10
0 2 5
1 3 1
1 2 2
2 1 3
2 1 5
2 3 9
2 4 2
3 4 4
3 4 8
4 3 6
4 0 7
stdout
copy 
10
https://ideone.com/qflxuF
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!