#include <iostream>
#include <map>
#include <string>
using namespace std;
int n;
int inf = 999999999;
int bus[201][201];
int book[151];
int main()
{
while (cin >> n && n != -1)
{
map<string, int> place;
place.clear();
int m = 2, t;
int dis[201];
string s1, e1;
cin >> s1 >> e1;
place[s1] = 0;
place[e1] = 1;
for (int i = 0; i < 151; i++)
for (int j = 0; j < 151; j++)
{
if (i == j) bus[i][j] = 0;
else bus[i][j] = inf;
}
for (int i = 0; i < n; i++)
{
string s, e;
cin >> s >> e >> t;
int x, y;
if (place.count(s) == 0)
{
place[s] = m;
x = m;
m++;
}
else x = place[s];
if (place.count(e) == 0)
{
place[e] = m;
y = m;
m++;
}
else y = place[e];
bus[x][y] = t;
bus[y][x] = t;
}
if (s1 == e1)
{
cout << 0 << endl;
continue;
}
for (int i = 0; i < m; i++)
{
dis[i] = bus[0][i];
book[i] = 0;
}
for (int i = 1; i < m; i++)
{
int min = inf;
int x = 0;
for (int j = 1; j < m; j++)
if (book[j] == 0 && min > dis[j])
{
x = j;
min = dis[j];
}
book[x]++;
if (min >= inf)
{
cout << -1 << endl;
break;
}
for (int j = 1; j < m; j++)
if (book[j] == 0 && dis[j] > dis[x] + bus[x][j])
dis[j] = dis[x] + bus[x][j];
if (x == 1)
{
cout << dis[1] << endl;
break;
}
}
}
}
Processed:
0.022, SQL:
9
