- Code: Select all
#include<iostream>
#include<utility>
#include<cstdio>
#include<vector>
#include<string>
#include<map>
#include<queue>
#define MAX_INT 1077952576
using namespace std;
int E,len;
int cost[2*2000+10],res;
bool visited[2*2000+10];
map<string,int>v;
vector< vector< pair< int,pair<int,char> > > > adjList(2000*2+10);
priority_queue<pair< int,pair<int,char> > > pq;
void initialize()
{
int i,j;
for(i = 0; i<=E*2; i++)
cost[i] = MAX_INT;
for(i =0; i<=E*2; i++)
visited[i] = false;
v.clear();
adjList.clear();
for(i=0;i<2*E;i++)
adjList[i].clear();
pq = priority_queue<pair< int,pair<int,char> > > ();
res = MAX_INT;
}
int main()
{
int i,j,k,u,d,cnt;
while(scanf("%d",&E)==1){
if(E==0)
break;
initialize();
string s1,s2,s3;
cin>>s1>>s2;
cnt = 2;
v[s1] = 0; //source vertex indexed to 0
if(v.find(s1) == v.find(s2)){
res = 0;
}
v[s2] = 1; //destination vertex indexed to 1
for(i=0; i<E; i++){
s1.clear();
s2.clear();
s3.clear();
cin>>s1>>s2>>s3;
if(v.find(s1) == v.end()){
v[s1] = cnt;
u = cnt++;
}
else
u = v.find(s1)->second;
if(v.find(s2) == v.end()){
v[s2] = cnt;
d = cnt++;
}
else
d = v.find(s2)->second;
len = s3.size();
char ch = s3[0];
adjList[u].push_back(make_pair(len,(make_pair(d,ch))));
adjList[d].push_back(make_pair(len,(make_pair(u,ch))));
}
//end of taking input
//Dijkstra Begins
cost[0] = 0;
pair<int,pair<int,char> > cur, next;
pq.push(make_pair(0,make_pair(0,'1')));
while(!pq.empty()){
cur = pq.top();
pq.pop();
cur.first = -cur.first;
if(visited[cur.second.first])
continue;
visited[cur.second.first] = true;
for(i = 0; i<adjList[cur.second.first].size(); i++){
next = adjList[cur.second.first][i];
if(next.second.second == cur.second.second)
continue;
if(visited[next.second.first])
continue;
int curcost = cost[cur.second.first] + next.first;
if(curcost < cost[next.second.first]){
cost[next.second.first] = curcost;
}
pq.push(make_pair(-curcost,make_pair(next.second.first,next.second.second)));
}
}
if( res ==0 )
printf("0\n");
else if(cost[1]== MAX_INT)
printf("impossivel\n");
else
printf("%d\n",cost[1]);
}
return 0;
}
Thanks in advance.