fork download
copy 
  1. #include <cstdio>
  2. #include <cmath>
  3. #include <cstring>
  4. #include <cstdlib>
  5. #include <climits>
  6. #include <queue>
  7. #include <algorithm>
  8. #include <vector>
  9. #include <iostream>
  10. #include <string>
  11.  
  12. using namespace std;
  13.  
  14. const int INF=0x10000000;
  15.  
  16. struct edge{
  17. 	int from,to;
  18. 	int cost;
  19. 	edge(int f,int t,int c){from=f;to=t;cost=c;}
  20. };
  21.  
  22. enum TYPE{HOME,CAKESHOP,CITYHALL,LANDMARK};
  23. struct node:public vector<edge>{
  24. 	TYPE type;
  25. 	int calorie;
  26. 	node(){type=LANDMARK;calorie=0;clear();}
  27. };
  28.  
  29. typedef vector<node> graph;
  30.  
  31. int Nodeno(string s,int m){//文字列から頂点番号を取得する
  32. 	if(s=="D")return 1;
  33. 	if(s=="H")return 0;
  34. 	if(s[0]=='L'){
  35. 		int r;
  36. 		sscanf(s.c_str(),"L%d",&r);
  37. 		return 2+m+(r-1);
  38. 	}else{
  39. 		int r;
  40. 		sscanf(s.c_str(),"C%d",&r);
  41. 		return 2+(r-1);
  42. 	}
  43. }
  44.  
  45. typedef pair<int,int> dijk_state; //時間と頂点の番号
  46. //ダイクストラ法
  47. vector<int> dijkstra(graph &Graph,int s){
  48. 	vector<int> result(Graph.size());
  49. 	std::fill(result.begin(),result.end(),INF);
  50. 	result[s]=0;
  51. 	priority_queue<dijk_state,vector<dijk_state>,greater<dijk_state> > que;
  52. 	for(unsigned int i=0;i<Graph[s].size();i++)que.push(dijk_state(Graph[s][i].cost,Graph[s][i].to));
  53. 	while(!que.empty()){
  54. 		dijk_state t=que.top();que.pop();if(result[t.second]<=t.first)continue;
  55. 		result[t.second]=t.first;
  56. 		if(Graph[t.second].type==CAKESHOP)continue; //ケーキ屋を通ったら、そこから別の所に移動することは出来ない
  57. 		for(unsigned int i=0;i<Graph[t.second].size();i++){
  58. 			if(result[Graph[t.second][i].to]<=t.first+Graph[t.second][i].cost)continue;
  59. 			que.push(dijk_state(t.first+Graph[t.second][i].cost,Graph[t.second][i].to));
  60. 		}
  61. 	}
  62. 	return result;
  63. }
  64.  
  65. //グラフからランドマークを消去する
  66. graph makeGraph(graph &Graph,int m){
  67. 	int V=2+m;
  68. 	graph result(V);
  69. 	result[0].type=HOME;result[1].type=CITYHALL;
  70. 	for(int i=0;i<m;i++){
  71. 		result[i+2].type=CAKESHOP;result[i+2].calorie=Graph[i+1].calorie;
  72. 	}
  73. 	for(int i=0;i<V;i++){
  74. 		vector<int> ret=dijkstra(Graph,i);
  75. 		for(int j=0;j<V;j++){
  76. 			if(ret[j]<INF){
  77. 				result[i].push_back(edge(i,j,ret[j]));
  78. 			}
  79. 		}
  80. 	}
  81. 	return result;
  82. }
  83.  
  84. struct BFS_state{
  85. 	int node;
  86. 	int accessed;
  87. 	int calorie;
  88. 	BFS_state(){}
  89. 	BFS_state(int n,int a,int c){node=n;accessed=a;calorie=c;}
  90. };
  91. //最小の消費カロリーを求める
  92. int MinimumCalorie(graph Graph){
  93. 	//BFS
  94. 	//O(m!*2^m)
  95. 	int result=INT_MAX;
  96. 	queue<BFS_state> que;
  97. 	que.push(BFS_state(0,0,0));
  98. 	while(!que.empty()){
  99. 		BFS_state t=que.front();que.pop();
  100. 		if(t.node==1){result=min(result,t.calorie);continue;}//市役所に到着
  101. 		t.accessed|=1<<t.node;
  102. 		if(t.node>=2){t.calorie-=Graph[t.node].calorie;}//ケーキ屋ならカロリーを入手出来る
  103. 		for(unsigned int i=0;i<Graph[t.node].size();i++){
  104. 			if((t.accessed>>Graph[t.node][i].to)&1)continue;
  105. 			que.push(BFS_state(Graph[t.node][i].to,t.accessed,t.calorie+Graph[t.node][i].cost));
  106. 		}
  107. 	}
  108. 	return result;
  109. }
  110.  
  111. int main(){
  112. 	while(1){
  113. 		int m,n,k,d;
  114. 		cin >> m >> n >> k >> d;
  115. 		int V=1+1+m+n;//頂点数は家(1)+市役所(1)+ケーキ屋の個数(m)+ランドマークの個数(n)
  116.  
  117. 		if(V==2)break;//V=2の時は終了
  118.  
  119. 		graph Graph(V);//グラフとして表す
  120. 		Graph[0].type=HOME;Graph[1].type=CITYHALL; //頂点0が家で、頂点1が市役所
  121. 		for(int i=0;i<m;i++){
  122. 			int t;cin >> t;Graph[i+2].type=CAKESHOP;Graph[i+1].calorie=t; //ケーキ屋である頂点の情報
  123. 		}
  124. 		for(int i=0;i<n;i++)Graph[i+2+m].type=LANDMARK; //ランドマークの情報の決定
  125.  
  126.  
  127. 		for(int i=0;i<d;i++){//全ての道の情報を得る
  128. 			string s1,s2;int D,c1,c2;
  129. 			cin >> s1 >> s2 >> D;
  130. 			c1=Nodeno(s1,m);c2=Nodeno(s2,m);
  131. 			Graph[c1].push_back(edge(c1,c2,D*k));
  132. 			Graph[c2].push_back(edge(c2,c1,D*k));
  133. 		}
  134.  
  135. 		cout << MinimumCalorie(makeGraph(Graph,m)) << endl; //グラフを簡略化してBFSする
  136.  
  137. 	}
  138. 	return 0;
  139. }
  140.  
Success #stdin #stdout 0s 2868KB
comments (?)
stdin
copy 
1 1 2 5
35
H L1 5
C1 D 6
C1 H 12
L1 D 10
C1 L1 20
2 1 4 6
100 70
H L1 5
C1 L1 12
C1 D 11
C2 L1 7
C2 D 15
L1 D 8
0 0 0 0
stdout
copy 
1
-2
https://ideone.com/QgeuV
language:
C++ (gcc 8.3)
created:
13 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!