fork(2) 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.  
  60. 			if(room[e2.to]==1){
  61. 				e2a.d=e2.d-e1a.d;
  62. 			}else{
  63. 				e2a.d=x-e1a.d;
  64. 			}
  65. 			cout<<"("<<e1a.to<<" "<<e1a.d<<" "<<e2a.d<<")";
  66. 			bool moveok=false;
  67. 			if(e2a.d<=0){
  68. 				e2a.d=0;
  69. 				e2a.state=room[e1a.to];
  70. 				moveok=true;
  71. 			}else if(room[e1a.to]==1){
  72. 				moveok=true;
  73. 			}else if(e2a.state=room[e1a.to]){
  74. 				moveok=true;
  75. 			}
  76. 			if(moveok==false)continue;
  77. 			pq.push(e2a);
  78. 		}
  79. 		cout<<endl;
  80. 	}
  81. 	int ans=-1;
  82. 	for(int i=0;i<=200;i++){
  83. 		long long int t1=dp[room[n]][i][n];
  84. 		if(ans==-1 || (t1!=-1 && t1<ans))ans=t1;
  85. 	}
  86. 	cout<<ans;
  87. 	return 0;
  88. }
Success #stdin #stdout 0.01s 67260KB
comments (?)
stdin
copy 
8 10 4
0
1
1
2
1
1
2
0
1 2 1
1 3 1
2 3 3
2 4 5
3 4 1
4 5 1
5 6 1
5 8 1
1 7 2
7 8 2
stdout
copy 
(0 0 1 4)
(2 1 3)(3 1 3)(7 2 2)
(1 0 2 3)
(1 1 2)(3 3 0)(4 5 -2)
(1 0 3 3)
(1 1 2)(2 3 0)(4 1 2)
(2 2 7 2)
(1 2 2)(8 2 2)
(2 2 4 2)
(2 5 -1)(3 1 3)(5 1 3)
(3 2 3 3)
(1 1 2)(2 3 0)(4 1 2)
(3 2 5 3)
(4 1 2)(6 1 2)(8 1 2)
(4 2 4 2)
(4 2 4 2)
(4 1 3 0)
(1 1 -1)(2 3 -3)(4 1 -1)
(4 1 2 0)
(1 1 -1)(3 3 -3)(4 5 -5)
(4 2 6 2)
(5 1 1)
(5 0 1 0)
(2 1 3)(3 1 3)(7 2 2)
(5 2 4 0)
(2 5 -1)(3 1 3)(5 1 3)
(5 2 5 1)
(4 1 0)(6 1 0)(8 1 0)
(5 0 1 0)
(6 1 2 0)
(6 2 5 3)
(6 1 6 0)
(5 1 -1)
(6 2 4 0)
(6 2 3 3)
(6 0 2 3)
(6 0 3 3)
(6 2 4 0)
(6 0 8 0)
(5 1 3)(7 2 2)
(7 2 7 2)
(7 1 5 0)
(4 1 -1)(6 1 -1)(8 1 -1)
(7 1 2 0)
(7 1 2 0)
(7 0 5 3)
(4 1 2)(6 1 2)(8 1 2)
(7 1 3 0)
(8 2 7 2)
(8 0 6 2)
(5 1 1)
(8 2 4 2)
(8 0 8 0)
(8 1 6 0)
(8 2 4 0)
(9 2 4 0)
(9 0 5 1)
(4 1 0)(6 1 0)(8 1 0)
(10 1 2 0)
(10 1 6 0)
(10 2 4 0)
(10 0 8 0)
6
https://ideone.com/701L4M
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!