Reserved Bus _ TA

#include<iostream>
#include<queue>


using namespace std;

#define OO 9999999
#define maxN 505
int n, k;
int cnt[maxN];
int Road[maxN][maxN];
int Road_len[maxN][maxN];
int dist[maxN][maxN];





class Node {
public:
	int city, length;

	Node(int c, int l)
	{
		city = c;
		length = l;
	}

	bool operator< (const Node& other) const {
		return length > other.length;
	}

};


void init(int N, int K, int mRoadAs[], int mRoadBs[], int mLens[])
{
	n = N;
	k = K;


	for (int i = 0; i <= n; i++)
	{
		cnt[i] = 0;
		for (int j = 0; j <= n; j++)
		{
			Road_len[i][j] = -1;
			dist[i][j] = OO;
		}
	}

	for (int i = 0; i < k; i++)
	{
		Road[mRoadAs[i]][cnt[mRoadAs[i]]++] = mRoadBs[i];
		Road[mRoadBs[i]][cnt[mRoadBs[i]]++] = mRoadAs[i];
		Road_len[mRoadBs[i]][mRoadAs[i]] = Road_len[mRoadAs[i]][mRoadBs[i]] = mLens[i];
	}
}

void addRoad(int mRoadA, int mRoadB, int mLen)
{
	Road[mRoadA][cnt[mRoadA]++] = mRoadB;
	Road[mRoadB][cnt[mRoadB]++] = mRoadA;
	Road_len[mRoadB][mRoadA] = Road_len[mRoadA][mRoadB] = mLen;

}

void Dijisktra(int Start, int e, int s)
{
	priority_queue<Node> pq;
	
	for (int i = 0; i <= n; i++)
	{
		dist[Start][i] = OO;
	}

	dist[Start][Start] = 0;
	pq.push({ Start, 0 });

	while (!pq.empty())
	{
		Node cur_city = pq.top(); pq.pop();

		if (cur_city.city == s || cur_city.city == e)	continue;

		for (int i = 0; i < cnt[cur_city.city]; i++)
		{
			int new_city = Road[cur_city.city][i];
			int l = Road_len[cur_city.city][new_city];

			if (l + dist[Start][cur_city.city] < dist[Start][new_city])
			{
				dist[Start][new_city] = l + dist[Start][cur_city.city];
				pq.push({ new_city, l + dist[Start][cur_city.city] });
			}

		}
	}
	
}

int findPath(int mStart, int mEnd, int M, int mStops[])
{
	cout << "s = " << mStart << endl;
	cout << "e = " << mEnd << endl;
	sort(mStops, mStops + M);

	for (int i = 0; i < M; i++)
	{
		Dijisktra(mStops[i], mEnd, mStart);
	}

	int ans = OO;

	do {
		int currDist = dist[mStops[0]][mStart];
		for (int i = 1; i < M; i++)
			currDist += dist[mStops[i - 1]][mStops[i]];
		currDist += dist[mStops[M - 1]][mEnd];
		ans = min(ans, currDist);

	} while (next_permutation(mStops, mStops + M));

	return ans == OO ? -1 : ans;
}






int main()
{
	int N = 7;
	int K = 10;
	int mRoadAs[] = { 1,1,1,2,2,3,3,4,4,5 };
	int mRoadBs[] = { 2,4,5,3,4,4,6,5,6,6 };
	int mLens[] = { 1,1,3,1,4,1,3,3,1,5 };

	init(N, K, mRoadAs, mRoadBs, mLens);

	int mStop[20] = { 2 };
	int res = findPath(1, 7, 1, mStop);
	cout << res << endl;
	addRoad(4, 7, 4);
	res = findPath(1, 7, 1, mStop);
	cout << res << endl;
	K = 2;
	int mStop1[2] = { 5, 7 };
	res = findPath(2, 1, 2, mStop1);
	cout << res << endl;

	K = 3;
	int mStop2[3] = { 6, 4 ,2};
	res = findPath(1, 5, K, mStop2);
	cout << res << endl;

	K = 3;
	int mStop3[3] = { 2, 5 ,6 };
	res = findPath(1, 4, K, mStop3);
	cout << res << endl;

	res = findPath(4, 1, K, mStop3);
	cout << res << endl;

	K = 3;
	int mStop4[3] = { 2, 3 ,7 };
	res = findPath(1, 4, K, mStop4);
	cout << res << endl;

	K = 1;
	int mStop5[1] = { 4 };
	res = findPath(5, 2, K, mStop5);
	cout << res << endl;

	return 0;
}