fork(1) download
copy 
  1. #include <iostream>
  2. #include <string.h>
  3. #include <vector>
  4. #include <queue>
  5. using namespace std;
  6.  
  7. struct E{
  8. 	int to,d;
  9. };
  10. struct E2{
  11. 	int to,state,d;
  12. 	long long int time;
  13. 	bool operator<(const E2& e2)const{
  14. 		return time>e2.time;
  15. 	}
  16. };
  17.  
  18.  
  19. long long int dp[4][203][10003];
  20. int room[10003];
  21. vector<E> cons[10003];
  22. int n,m,x;
  23. int main() {
  24. 	memset(dp,-1,sizeof(dp));
  25. 	cin>>n>>m>>x;
  26. 	for(int i=1;i<=n;i++){
  27. 		cin>>room[i];
  28. 	}
  29. 	for(int i=0;i<m;i++){
  30. 		int from,to;
  31. 		E e1;
  32. 		cin>>from>>to>>e1.d;
  33. 		e1.to=to;
  34. 		cons[from].push_back(e1);
  35. 		e1.to=from;
  36. 		cons[to].push_back(e1);
  37. 	}
  38. 	E2 e2;
  39. 	e2.to=1;
  40. 	e2.state=room[1];
  41. 	e2.time=0;
  42. 	e2.d=x;
  43. 	priority_queue<E2> pq;
  44. 	pq.push(e2);
  45. 	while(pq.size()>0){
  46. 		E2 e2=pq.top();
  47. 		//cout<<"("<<e2.time<<" "<<e2.state<<" "<<e2.to<<" "<<e2.d<<")"<<endl;
  48. 		pq.pop();
  49. 		long long int t1=dp[e2.state][e2.d][e2.to];
  50. 		if(t1!=-1 && t1<=e2.time)continue;
  51. 		dp[e2.state][e2.d][e2.to]=e2.time;
  52. 		for(auto it=cons[e2.to].begin();it!=cons[e2.to].end();it++){
  53. 			E e1a=(*it);
  54.  
  55. 			E2 e2a;
  56. 			e2a.to=e1a.to;
  57. 			e2a.state=e2.state;
  58. 			e2a.time=e2.time+e1a.d;
  59. 			e2a.d=e2.d-e1a.d;
  60. 			if(e2a.d<=0)e2a.d=0;
  61. 			bool moveok=false;
  62. 			if(e2a.d<=0){
  63. 				moveok=true;
  64. 				e2a.state=room[e1a.to];
  65. 				if(room[e1a.to]==1){
  66. 					e2a.d=0;
  67.  
  68. 				}else{
  69. 					e2a.d=x;
  70. 				}
  71. 			}else{
  72. 				if(room[e1a.to]==1 || room[e1a.to]==e2a.state){
  73. 					moveok=true;
  74. 				}
  75. 				if(room[e1a.to]==e2a.state && room[e1a.to]!=1){
  76. 					e2a.d=x;
  77. 				}
  78. 			}
  79. 			//cout<<"("<<e1a.to<<" "<<e1a.d<<" "<<e2a.d<<")";
  80. 			if(moveok==false)continue;
  81. 			pq.push(e2a);
  82. 		}
  83. 	}
  84. 	int ans=-1;
  85. 	for(int i=0;i<=200;i++){
  86. 		long long int t1=dp[room[n]][i][n];
  87. 		if(ans==-1 || (t1!=-1 && t1<ans))ans=t1;
  88. 	}
  89. 	cout<<ans;
  90. 	return 0;
  91. }
Success #stdin #stdout 0.02s 67232KB
comments (?)
stdin
copy 
15 25 4
0
1
1
0
2
1
0
1
1
2
0
0
1
0
1
8 11 1
7 10 1
12 14 1
3 8 1
1 5 1
3 9 1
3 8 1
1 5 1
6 15 1
11 12 1
2 14 1
7 10 1
11 12 1
5 13 1
2 8 1
1 4 1
2 11 1
5 6 1
1 13 1
6 12 1
5 10 1
9 13 1
4 10 1
3 12 1
7 13 1
stdout
copy 
8
https://ideone.com/BB4ttM
language:
C++ (gcc 8.3)
created:
1 day 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!