fork download 
  1. /*input
  2. 2
  3. a b
  4. a b abcd
  5. a b abc
  6. 0
  7. */
  8.  
  9. #include <bits/stdc++.h>
  10.  
  11. using namespace std;
  12.  
  13. typedef unsigned long long int ull;
  14. typedef long long ll;
  15. typedef pair<int,int> ii;
  16. typedef vector<int> vi;
  17. typedef vector<ii> vii;
  18.  
  19. #define rep(i,a,n) for (int i=a;i<n;i++)
  20. #define per(i,a,n) for (int i=n-1;i>=a;i--)
  21. #define all(x) (x).begin(),(x).end()
  22. #define sz(x) ((int)(x).size())
  23. #define pb push_back
  24. #define mp make_pair
  25. #define pq priority_queue
  26. #define fi first
  27. #define se second
  28. #define INF    0x3f3f3f3f
  29. #define NEGINF 0xC0C0C0C0
  30. #define LINF   0x3f3f3f3f3f3f3f3fLL
  31. #define EPS 1e-10
  32. #define PI 2 * acos(0)
  33. #define NULO -1
  34. #define endl '\n'
  35.  
  36. const ll mod=1000000007;
  37. ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
  38.  
  39. int cmp(double x, double y = 0, double tol = EPS){ return (x <= y + tol) ? (x + tol < y) ? -1 : 0 : 1; }
  40.  
  41. map<string, int> mapa;
  42. int idx;
  43.  
  44. int insere(string s){
  45. 	if(mapa.find(s)!=mapa.end())return mapa[s];
  46. 	return mapa[s]=idx++;
  47. }
  48.  
  49. int main(){
  50. 	string o,d,a,b,c;
  51. 	int n,origem, destino;
  52. 	while(scanf("%d ",&n) and n){
  53. 		vector< vector<pair<int,string> > > adj(n*2+10,vector<pair<int, string> >());
  54. 		idx=0;
  55. 		cin>>o>>d;
  56. 		mapa.clear();
  57. 		origem=insere(o);
  58. 		destino=insere(d);
  59. 		rep(i,0,n){
  60. 			cin>>a>>b>>c;
  61. 			adj[insere(a)].pb(mp(insere(b),c));
  62. 			adj[insere(b)].pb(mp(insere(a),c));
  63. 			//cout<<a<<b<<" ";
  64. 			//printf("%d %d\n",insere(b),insere(a));
  65. 		}
  66.  
  67. 		int dist[4005][26];
  68. 		rep(i,0,4005)
  69. 			rep(j,0,26)
  70. 				dist[i][j]=1<<30;
  71. 		//memset(dist,1<<30,sizeof dist);
  72. 		rep(i,0,26)
  73. 			dist[origem][i]=0;	
  74. 		pq<pair<int,char>,vector<pair<int,char> >, greater<pair<int,char> > > q;
  75. 		q.push(mp(origem,o[0]));
  76. 		while(!q.empty()){
  77. 			pair<int,char> front=q.top(); q.pop();
  78. 			int v = front.fi;
  79. 			char cx = front.se;
  80. 			rep(i,0,adj[v].size()){
  81. 				pair<int,string> aux = adj[v][i];
  82. 				int u = aux.fi;
  83. 				char c = aux.se[0];
  84. 				if(c == cx) continue;
  85. 				if(dist[u][c-'a']>=dist[v][cx-'a']+aux.se.size()){
  86. 					//printf("%d\n",u);
  87. 					dist[u][c-'a']=dist[v][cx-'a']+aux.se.size();
  88. 					q.push(mp(u,c));
  89. 				}
  90. 			}
  91. 		}
  92. 		int ans=1<<30;
  93. 		rep(i,0,26)
  94. 			ans=min(ans,dist[destino][i]);
  95. 		if(ans==1<<30)printf("impossivel\n");
  96. 		else printf("%d\n",ans);	
  97. 	}
  98.  
  99.  
  100.  
  101. return 0;
  102. }
Success #stdin #stdout 0s 15528KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/B9iVyJ
language:
C++ (gcc 8.3)
created:
8 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!