fork download
  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
stdin
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
10