fork download 
  1. #include<stdio.h>
  2. #include<vector>
  3. #include<map>
  4. #include<set>
  5. #include<iostream>
  6. #include<algorithm>
  7. using namespace std;
  8. #define maxn 222222
  9. map<pair<int,int>,long long>hash;
  10. set<pair<long long, pair<int,int> > >pQ;
  11. set<int>S;
  12. char dump[1025];
  13. int n,m,k,i,j,x,y,repaint[maxn],ax[maxn],ay[maxn],color[maxn],z;
  14. long long he,dst,ans[maxn];
  15. vector<pair<int,int> >v[maxn];
  16. void push(int x,int y,long long z){
  17. 	if(x==y)return;
  18. 	if(hash.count(make_pair(x,y))&&hash[make_pair(x,y)]<=z)return;
  19. 	if(hash.count(make_pair(x,y))){
  20. 		he=hash[make_pair(x,y)];
  21. 		if(pQ.find(make_pair(he,make_pair(x,y)))!=pQ.end())pQ.erase(pQ.find(make_pair(he,make_pair(x,y))));
  22. 	}
  23. 	hash[make_pair(x,y)]=z;
  24. 	pQ.insert(make_pair(z,make_pair(x,y)));
  25. }
  26. void give(long long k,int x,int y,int l,int r){
  27. 	set<int>::iterator it;
  28. 	while(1){
  29. 		it=S.lower_bound(l);
  30. 		if(it==S.end())return;
  31. 		if(*it>r)return;
  32. 		ans[*it]=k;ax[*it]=x;ay[*it]=y;
  33. 		S.erase(it);
  34. 	}
  35. }
  36. int main(){
  37. 	freopen("parties.in","r",stdin);
  38. 	freopen("parties.out","w",stdout);
  39. 	scanf("%d%d%d",&n,&m,&k);gets(dump);
  40. 	for(i=1;i<=n;i++)color[i]=(getchar()=='L');
  41. 	for(i=1;i<=m;i++){
  42. 		scanf("%d%d%d",&x,&y,&z);
  43. 		v[x].push_back(make_pair(z,y));
  44. 		v[y].push_back(make_pair(z,x));
  45. 		push(min(x,y),max(x,y),z);
  46. 	}
  47. 	for(i=1;i<=n;i++)repaint[i]=n+1;
  48. 	for(i=1;i<=k;i++){
  49. 		scanf("%d",&x);
  50. 		repaint[x]=i;
  51. 	}
  52. 	for(i=0;i<=k;i++)S.insert(i);
  53. 	while(pQ.size()&&S.size()){
  54. 		dst=pQ.begin()->first;x=pQ.begin()->second.first;y=pQ.begin()->second.second;pQ.erase(pQ.begin());
  55. 		if(color[x]==color[y]){
  56. 			give(dst,x,y,0,min(repaint[x],repaint[y])-1);
  57. 			give(dst,x,y,max(repaint[x],repaint[y]),n);
  58. 		}else give(dst,x,y,min(repaint[x],repaint[y]),max(repaint[x],repaint[y])-1);
  59. //		if(color[x]!=color[y]){
  60. 		for(i=0;i<v[x].size();i++)push(v[x][i].second,y,dst+v[x][i].first);
  61. 		for(i=0;i<v[y].size();i++)push(x,v[y][i].second,dst+v[y][i].first);
  62. //		}
  63. 	}
  64. 	for(i=0;i<=k;i++)cout<<ans[i]<<" "<<ax[i]<<" "<<ay[i]<<endl;
  65. 	return 0;
  66. }
  67.  
Success #stdin #stdout 0.01s 10672KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/jHrWR
language:
C++ (gcc 8.3)
created:
12 years 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!