Dijkstra

main.cpp

#include <iostream>
#include <set>
#include <map>
#include <algorithm>
#include <vector>

#define JudgeInfinity (INT_MAX >> 1)

using namespace std;

typedef struct Edge{
	int iLength;
	unsigned int iNode;
	Edge(int l, int n){ iLength = l; iNode = n; }
	bool operator<(const Edge& e) const { return this->iNode < e.iNode; }
}Edge;

typedef struct Vertex{
	int val;

	bool visit;
	int weight;
	set<Edge> edges;
	vector<int> route;

	Vertex& operator=(int n){
		weight = n;
		return *this;
	}

	Vertex() { visit = false; val = 0; weight = JudgeInfinity; }
	void insert(int l, int n) { edges.insert(Edge(l, n)); }
	bool operator<(const Vertex& e) const { return this->weight < e.weight; }

}Vertex;

int SelectMinPath(const map<int, Vertex>& g)
{
	int minpath = JudgeInfinity;
	int minNode = g.begin()->first;

	for (auto &p : g)
		if (!p.second.visit && p.second.weight <= minpath)
		{
			minpath = p.second.weight;
			minNode = p.first;
		}
	return minNode;
}

int main()
{
	map<int, Vertex> graph_path;
	//  node,edge, start node
	int N, M, S;

	cin >> N >> M >> S;

	int fromNode, ToNode, NtoN_length;

	for (int i = 0; i < M; ++i)
	{
		cin >> fromNode >> ToNode >> NtoN_length;
		graph_path[fromNode].insert(NtoN_length, ToNode);
	}

	// first visit
	graph_path[S] = 0;

	for (int i = 0; i < graph_path.size(); ++i)
	{
		int inowNode = SelectMinPath(graph_path);
		auto &nowNode = graph_path[inowNode];
		nowNode.visit = true;
		nowNode.route.push_back(inowNode);
		for (auto &p : nowNode.edges)
		{
			//  new vs old -> new win !
			if (nowNode.weight + p.iLength < graph_path[p.iNode].weight)
			{
				graph_path[p.iNode].weight = nowNode.weight + p.iLength;
				graph_path[p.iNode].route = nowNode.route;
			}
		}
	}

	// output
	for (auto &p : graph_path)
	{
		if (p.second.weight == JudgeInfinity)
			cout << "no search!";
		else for (auto q : p.second.route)
			cout << q << " ";
		cout << endl;
	}

}