#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <list>
using namespace std;

struct Edge{ int to; int wt; };

struct City{ string name; list<Edge> adj; };

class PathFinder{
private:
	map<string,int> name2idx;
	vector<City> city;
	
public:
	PathFinder(string fileName); //builds graph from file
	int minCost(string from, string to); //-1 if no path

private:  //helper methods==================
	
	typedef map<string,int>:: iterator Iter;	      //map iterator
	typedef list<Edge>::iterator eIter;			//list iterator

	int addEdge(int to, int wgt);				  //build graph
	int addCity(string from);				   //build graph
	int pushCity(string city);
	int pushEdge(string from, string to, int wgt);

};

#include "pathfinder.h"
#include <fstream> 
#include <iostream>


PathFinder::PathFinder(string fileName){

	ifstream fin(fileName.c_str());

	while(true){
		
		string from, to; 
		int wgt = 0;
        fin>>from>>to>>wgt;	 if(!fin) break;	

		//add cities
		pushCity(from);
		pushCity(to);

		//add edges
		pushEdge(from, to, wgt);

	}

	/*
	//check adjacencies test loop
	for(unsigned int i = 0; i< city.size(); i++){
		eIter begin = city[i].adj.begin();
		eIter end = city[i].adj.end();

		while( begin != end) {
			//get city from index number
			City ct = city[begin->to];
			//cout<<begin->to<<" can be reached from "<<city[i].name<<endl;
			++begin;
		}
	}
	*/
	//cout<<name2idx.size()<<"= ="<<city.size()<<endl;
	for(int i=0;i<city.size();i++){
		cout<<city[i].name<<": ";
		for(list<Edge>::iterator it=city[i].adj.begin();
	        it != city[i].adj.end(); it++)
		cout<<city[it->to].name<<","<<it->wt<<" ";
		cout<<endl;
	}
}

int PathFinder::minCost(string from, string to){
	//returns cheapest path or -1 if not found

	int MAX_INT= 2500000;
	bool once = true;
	int trueCount = 0;	 //infinite loop prevention (in theory)


	/* initialize arrays
	*/

	bool * isMarked = new bool[(int)city.size()];	 //true if marked
	for(int i = 0; i< (int)city.size(); i++){		 //init to false
		isMarked[i] = false;
	}

	int *cost = new int[(int)city.size()];			//travel cost
	for(int i = 0; i< (int)city.size(); i++){		//init to MAX_INT
		cost[i] = MAX_INT;
	}

	int curCityIndex = 0;

	/*//test loop
	for(int i = 0; i<100; i++){
			cout<<" City at i is "<<city[i].name<<endl;
	}
*/
	while (from != to){
		//get current city (from) index
		curCityIndex =name2idx.find(from)->second;
		cout<<"curcity=="<<from<<"=="<<endl;

 
		//set cost of initial starting city
		if(once){
			cost[curCityIndex]=0;			//sets initial cost to zero
			once = false;
			trueCount++;
		}

		/*******************UPDATE COSTS**********************/

		eIter begin = city[curCityIndex].adj.begin();
		eIter end = city[curCityIndex].adj.end();

		//if(city[curCityIndex].adj.size() == 0)return -1;

		while( begin != end && city[curCityIndex].adj.size() > 0 ) { //while not at end, and has adj.

			if(isMarked[begin->to]== false){

				int adj = begin->to;     //city to go to
				int weight = begin->wt;  //weighted cost
				
				if(cost[adj]  > cost[curCityIndex] + begin->wt){
					cost[adj] = cost[curCityIndex] + begin->wt;
			    }
			}
			++begin;
		}

		/****************FIND CHEAPEST NEXT********************/
		int cheapest = MAX_INT;
		int cheapIndex = MAX_INT;

		for(int i = 0; i< (int)city.size(); i++){
			

			if(cost[i]< cheapest && !isMarked[i]){
				cheapest = cost[i];
				cheapIndex = i;
				//from = city[i].name;

				//isMarked[i] = true;
				//trueCount++;

				//if(from == to && isMarked){
				//	return cost[i];
				//}
			}			
		}
		if(cheapIndex==MAX_INT)return -1;
		isMarked[cheapIndex]=true;
		from = city[cheapIndex].name;

	}

	return cost[name2idx.find(from)->second]; //if no path
	
}
//private helpers ====================




int PathFinder::pushEdge(string from, string to, int wgt){
	//post:push new edge

	Iter it = name2idx.find(to);
	Edge goTo;									
	goTo.to = it->second; 
	goTo.wt = wgt;
	
	city[name2idx.find(from)->second].adj.push_back(goTo);

	return 0;
}

int PathFinder::addCity(string from){
	//post: city is added to city and name2idx
	City start;									
	start.name = from;
	city.push_back(start);
	int thisI = (int)city.size()-1;
	//cout<<thisI<<"added city "<<from<<" idx="<<(int)name2idx.size()<<endl;
	name2idx.insert(make_pair(from,(int) name2idx.size()));

	return 0;
}

int PathFinder::pushCity(string city){
	//post: city is added to city and name2idx
	//      else return -1
	Iter it = name2idx.find(city);

	if( it==name2idx.end()) {
		addCity(city);	
		return 0;
	}

	return -1;				//if not added
}


//test program
int main(){
	PathFinder pf("flight.txt");
	while(true){
		string fr,to;
		cout<<"enter from to (q q to quit) ";cin>>fr>>to;
		if(fr=="q" && to=="q") break;
		cout<<pf.minCost(fr,to)<<endl;
	}
}

alpha bravo 1
bravo charlie 2
bravo delta 4
bravo echo 8
charlie echo 5
charlie delta 7
delta echo 6