dijkstra.cpp

void dijkstra() {
	//Dijkstra initialization
	vector<vector<double>> d(i_num, vector<double>(i_num, INF));
	vector<vector<bool>> used(i_num, vector<bool>(i_num));
	vector<int> pred(i_num);
	priority_queue<Vertex> q;

	// Dijkstra (modified)
	//d[snum] = 0;
	for (auto e : g[snum]) {
		d[e][snum] = 0;
		q.push({ 0, e, snum });
	}
	while (!q.empty()) {
		auto v = q.top();
		//out << v.num << " " << v.level << "\n";
		q.pop();
		if (used[v.num][v.prev])
			continue;
		used[v.num][v.prev] = 1;
		Ptd first_vec = vert[v.num] - vert[v.prev];
		for (auto e : g[v.num]) {
			if (used[e][v.num])
				continue;
			Ptd second_vec = vert[e] - vert[v.num];
			auto w = angle(first_vec, second_vec);
			if (d[e][v.num] > d[v.num][v.prev] + w) {
				d[e][v.num] = d[v.num][v.prev] + w;
				q.push({ d[e][v.num], e, v.num });
			}
		}
	}
	auto mn = *min_element(d[tnum].begin(), d[tnum].end());

	if (mn == INF) {
		printf("-1");
	}
	else {
		printf("%f\n", mn * 180 / M_PI);
	}
}