fork download
copy 
  1. //It's all about what U BELIEVE
  2. #include<algorithm>
  3. #include<iostream>
  4. #include<stdio.h>
  5. #include<cstring>
  6. #include<vector>
  7. #include<bitset>
  8. #include<stack>
  9. #include<queue>
  10. #include<deque>
  11. #include<cmath>
  12. #include<map>
  13. #include<set>
  14. #define endl '\n'
  15. #define PI acos(-1)
  16. #define INF ~(1<<31)
  17. #define pb push_back
  18. #define pob pop_back
  19. #define lsone(Z) (Z&-Z)
  20. #define modulo 1000000007
  21. #define gcu getchar_unlocked
  22. #define allof(Z) Z.begin(),Z.end()
  23. #define rallof(Z) Z.rbegin(),Z.rend()
  24. #define mset(z,v) memset(z,v,sizeof(z))
  25. #define lne if(line)puts("");else line =1
  26. #define fo(s,y,z) for(int y=s ; y<(int)z ; y++)
  27. #define readf freopen("/home/ebram96/Desktop/in" , "r" , stdin);
  28. #define writef freopen("/home/ebram96/Desktop/out" , "w" , stdout);
  29. using namespace std;
  30. typedef unsigned long long ull;
  31. typedef pair<ull,ull> pairull;
  32. typedef pair<int,int> pairii;
  33. typedef vector<string> vstr;
  34. typedef deque<int> dqint;
  35. typedef set<ull> setull;
  36. typedef unsigned int ui;
  37. typedef queue<int> qint;
  38. typedef vector<int> vi;
  39. typedef set<int> seti;
  40. typedef long long ll;
  41. //int dx[]={-1,0,1, 0,-1,1, 1,-1};
  42. //int dy[]={ 0,1,0,-1, 1,1,-1,-1};
  43. struct State
  44. {
  45. 	int u;
  46. 	ll w;
  47. 	inline bool operator<(const State &s)const
  48. 	{return s.w!=w?s.w<w:s.u<u;}
  49. };
  50. struct Rule
  51. {int u , v; ll w;};
  52. Rule r[1000];
  53. int t , n , m , source , destination , u , v , c;
  54. ll res , w , dist[1<<12];
  55. inline int get_set()
  56. {
  57. 	int ret = 0 , crystal , sz;
  58. 	scanf("%d",&sz);
  59. 	fo(0,y,sz)
  60. 	{
  61. 		scanf("%d",&crystal);
  62. 		ret|=(1<<crystal);
  63. 	}
  64. 	return ret;
  65. }
  66. inline ll dijkstra()
  67. {
  68. 	priority_queue<State>pq;
  69. 	pq.push({source,0});
  70. 	fo(0,y,1<<n)dist[y] = ull(-1);
  71. 	dist[source] = 0;
  72. 	while(!pq.empty())
  73. 	{
  74. 		u = pq.top().u , w = pq.top().w;
  75. 		if(u==destination)return w;
  76. 		pq.pop();
  77. 		if(w>dist[u])continue;
  78. 		fo(0,y,m)if((u&r[y].u)==r[y].u)
  79. 			if(w+r[y].w<dist[(u^r[y].u)|r[y].v])
  80. 			{
  81. 				pq.push({(u^r[y].u)|r[y].v,w+r[y].w});
  82. 				dist[(u^r[y].u)|r[y].v] = w+r[y].w;
  83. 			}
  84. 	}
  85. 	return -1;
  86. }
  87. int main()
  88. {
  89. 	//readf
  90. 	scanf("%d",&t);
  91. 	while(t--)
  92. 	{
  93. 		scanf("%d %d",&n,&m);
  94. 		source = get_set();
  95. 		destination = get_set();
  96. 		fo(0,y,m)
  97. 			scanf("%lld %d %d",&r[y].w,&r[y].u,&r[y].v);
  98. 		res = dijkstra();
  99. 		printf("Case #%d: ",++c);
  100. 		~res?printf("YES %lld\n",res):puts("NO");
  101. 	}
  102. }
  103.  
Success #stdin #stdout 0s 15288KB
comments (?)
stdin
copy 
2
1 1
1 0
1 0
1 1 0 1 0
3 1
2 0 1
1 2
1000000000 1 1 1 2
stdout
copy 
Case #1: YES 0
Case #2: NO
https://ideone.com/9Ngbyu
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

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!