#include<iostream>
#include<iomanip>
#include<cstdlib>
#include<cstdio>
#include<unordered_map>
#include<set>
#include<cmath>
#include<string.h>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<unordered_set>
#include<vector>
#include<deque>
#include<stack>
#define MAXSIZE 400
#define oo 1000000000000000000
using namespace std;
unordered_map<long long, string>id;
unordered_map<string, long long>cities;
vector<pair<long long, long long>>v_graph[100008];
string city1, city2;
long long cost, cost1, cost2;
long long adj_matrix[MAXSIZE][MAXSIZE];
long long Floyd_Arr[MAXSIZE][MAXSIZE];
long long n_cities, n_edges;
string ArrCities[MAXSIZE];
map<pair<long long, long long>, vector<long long> > Floyd_Path;
void Input()
{
cout << "please enter the number of cities .\n";
cin >> n_cities;
if (n_cities) cout << "\nPlease Enter the names of the cities \n";
for (int i = 0; i < n_cities; ++i)
{
cin >> ArrCities[i];
cities[ArrCities[i]] = i;
id[i] = ArrCities[i];
}
cout << "\nEnter the Number Of Edges You Want To ADD \n";
cin >> n_edges;
cout << "\nEnter The First City Then The Second City Then The Cost Of the Edge \n";
while (n_edges)
{
cin >> city1 >> city2 >> cost;
if (city1 == city2){
cout << "\nPlease Enter Different Names For City 1 And City 2 \n";
continue;
}
if (!cities.count(city1)) {
cout << "\nCity One Isn't in the Cities You Entered ,Please Enter Valid Names \n";
continue;
}
if (!cities.count(city2)){
cout << "\nCity Two Isn't in the Cities You Entered ,Please Enter Valid Names \n";
continue;
}
v_graph[cities[city1]].push_back({ cities[city2], cost });
v_graph[cities[city2]].push_back({ cities[city1], cost });
n_edges--;
}
}
void fill_matrix()
{
for (int i = 0; i < n_cities; i++) // initializing the adjacency matrix with infinity except the self edges
{
for (int j = 0; j < n_cities; j++)
{
Floyd_Arr[i][j] = -1; // Floyd_Arr Is used In Printing The Path
if (i == j)adj_matrix[i][j] = 0;
else
adj_matrix[i][j] = oo;
}
}
for (int i = 0; i < n_cities; i++)// filling up the adjacency matrix
{
for (int j = 0; j < v_graph[i].size(); j++)
{
adj_matrix[i][v_graph[i][j].first] = v_graph[i][j].second;
}
}
}
void Print_Floyd_Path(long long Source, long long Distination)
{
if (Floyd_Arr[Source][Distination] == -1)
{
cout << id[Source] << " " << id[Distination] << "\n";
return;
}
Print_Floyd_Path(Source, Floyd_Arr[Source][Distination]); // Printing All Intermediate Nodes
Print_Floyd_Path(Floyd_Arr[Source][Distination], Distination);
}
void Floyed_Warchall(long long i, long long j)
{
// The Algorithm works on connected Graphs
fill_matrix();
for (long long k = 0; k < n_cities; k++) // k Will Act As Intermediate node
for (long long i = 0; i < n_cities; i++)// i And j Traverse The Adjacency matrix
for (long long j = 0; j < n_cities; j++)
{
if (adj_matrix[i][k] + adj_matrix[k][j] < adj_matrix[i][j])
{
adj_matrix[i][j] = adj_matrix[i][k] + adj_matrix[k][j];
Floyd_Arr[i][j] = k; // This Arr is For Printing The Path
}
}
if (adj_matrix[i][j] == oo)
{ cout << "There's No Path Between " << id[i] << " And " << id[j] << "\n"; return; }
cout << "The Cost Between " << id[i] << " And " << id[j] << "is "<<adj_matrix[i][j]<<"\n";
cout << "\n\n";
Print_Floyd_Path(i, j);
}
int main()
{
Input();
cin >> city1 >> city2;
int i = cities[city1], j = cities[city2];
Floyed_Warchall(i, j);
//system("pause");
return 0;
}