uvaProblems/11492.cpp at master · 19mddill/uvaProblems · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include<bits/stdc++.h>
#define Fin          freopen("input.txt","r",stdin)
#define Fout         freopen("output.txt","w",stdout)

using namespace std;


using pii = pair<int,pair<string,bool> >; /**<language<word,visited> >**/
using px = pair< pair<int,char>, int >; /**< < total len,last letter>,language >**/


int dijkstra(vector< vector< pii > > &G,int source_lan,int des_lan){
	priority_queue<px> pq;
	pq.push(make_pair(make_pair(0,'#'),source_lan));

	while(!pq.empty()){
		px p = pq.top();
		pq.pop();
		int curr_val = p.first.first;
		char cc = p.first.second;
		int u = p.second;

		if(u == des_lan) return -curr_val;

		for(int i = 0;i< (int)G[u].size();i++){
			char uv_char = G[u][i].second.first[0];
			int uv_cost = G[u][i].second.first.size();
			int v = G[u][i].first;

			if( !G[u][i].second.second and uv_char != cc){
				int x = -curr_val + uv_cost;
				pq.push(make_pair(make_pair(-x,uv_char),v));
				G[u][i].second.second = true;
			}
		}
	}
	return -1;
}

int main(){
	//Fin;
	//Fout;
	int n;
	while(cin>>n,n){
		//cin.ignore();
		string source,destination;
		vector< vector< pii> >G;
		map<string,int>mp;

		cin>>source>>destination;

		int _n = n;
		int graph_index = 0;
		string x,y,w;

		while(_n--){
			cin>>x>>y>>w;

			if(mp.find(x) == mp.end()){
				mp[x] = graph_index;
				graph_index++;
				G.push_back( vector< pii >());
			}

			if(mp.find(y) == mp.end()){
				mp[y] = graph_index;
				graph_index++;
				G.push_back(vector< pii >());
			}
			G[mp[x]].push_back(make_pair(mp[y],make_pair(w,false)));
			G[mp[y]].push_back(make_pair(mp[x],make_pair(w,false)));
		}
		if(mp.find(source) == mp.end() or mp.find(destination) == mp.end()){
			cout<<"impossivel"<<endl;
		}else{
			int cost;
			cost =  dijkstra(G,mp[source],mp[destination]);
			if(cost < 0){
				cout << "impossivel" << endl;
			}else{
				cout<<cost<<endl;
			}

		}
	}

}