2345_Cost_and_Time_TA

//#pragma wanring (disable:4996)
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
#include<queue>
#include<set>


using namespace std;

#define maxN 105
#define inf 99999999
int n, k;

class State {
public:
	int cost, time;
	
	State(int c, int t)
	{
		cost = c;
		time = t;
	}
};

class Point {
public:
	int city, cost, time;

	Point(int c, int co, int t)
	{
		city = c;
		cost = co;
		time = t;
	}

	bool operator< (const Point& otherPoint) const {
		return time > otherPoint.time;
	}
};

int adj[maxN][maxN];
int cnt[maxN];

std::vector<State> Road[maxN][maxN];

int time_to_dest[maxN][maxN];

void init(int N, int K, int sCity[], int eCity[], int mCost[], int mTime[])
{
	n = N;
	for (int i = 0; i < N; i++)
	{
		cnt[i] = 0;
		for (int j = 0; j < N; j++)
		{
			time_to_dest[i][j] = inf;
			Road[i][j].clear();
		}
	}

	for (int i = 0; i < K; i++)
	{
		adj[sCity[i]][cnt[sCity[i]]++] = eCity[i];
		Road[sCity[i]][eCity[i]].push_back({ mCost[i], mTime[i] });
	}

}

void add(int sCity, int eCity, int mCost, int mTime)
{
	//adj[sCity][cnt[sCity]++] = eCity;
	if (Road[sCity][eCity].size() > 1)
	{
		Road[sCity][eCity].push_back({ mCost, mTime });
	}
	else
	{
		adj[sCity][cnt[sCity]++] = eCity;
		Road[sCity][eCity].push_back({ mCost, mTime });
	}
}

int cost(int M, int sCity, int eCity)
{
	Point res(eCity, inf, inf);

	for (int i = 0; i < maxN; i++)
	{
		time_to_dest[sCity][i] = inf;
	}

	priority_queue<Point> pq;

	time_to_dest[sCity][sCity] = 0;

	pq.push({ sCity, 0, 0 });

	//cout << "sCity = " << sCity << endl;

	while (!pq.empty())
	{
		Point cur_p = pq.top(); pq.pop();

		//cout << "cur_p.city = " << cur_p.city << endl;
		if (cur_p.city == eCity)
		{
			if (res.time > time_to_dest[sCity][eCity])
			{
				res.time = time_to_dest[sCity][eCity];
			}
		}
		for (int i = 0; i < cnt[cur_p.city]; i++)
		{
			int new_city = adj[cur_p.city][i];

			for (int j = 0; j < Road[cur_p.city][new_city].size(); j++)
			{
				int time = Road[cur_p.city][new_city][j].time;
				int cost = Road[cur_p.city][new_city][j].cost;

				if (cur_p.cost + cost <= M /*&& time_to_dest[sCity][cur_p.city] + time < time_to_dest[sCity][new_city]*/)
				{
					time_to_dest[sCity][new_city] = cur_p.time + time;
					pq.push({ new_city, cur_p.cost + cost, cur_p.time + time });
				}
			}

		}
	}

	//cout << time_to_dest[sCity][eCity] << endl;
	//return time_to_dest[sCity][eCity] == inf ? -1 : time_to_dest[sCity][eCity];
	return res.time == inf ? -1 : res.time;
}


int main()
{
	//freopen("input.txt", "r", stdin);
	int sCity[3] = { 0, 1, 3 };
	int eCity[3] = { 1, 3, 4 };
	int mCost[3] = { 80, 70, 20 };
	int mTime[3] = { 50, 20, 10 };

	init(5, 3, sCity, eCity, mCost, mTime);
	int res = cost(200, 1, 2);
	cout << res << endl;
	res = cost(200, 0, 4);
	cout << res << endl;
	add(0, 2, 20, 30);
	add(2, 1, 40, 40);
	add(1, 3, 10, 60);
	res = cost(120, 0, 4);
	cout << res << endl;
	res = cost(100, 0, 4);
	cout << res << endl;
	return 0;
}