743.cpp

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int N, int K) {
		// first v, second w
		vector<vector<pair<int, int> > > adj(N+1, vector<pair<int, int> >());
		// dist and parent
		vector<pair<int, int> > dist_p(N+1, make_pair(INT_MAX, -1));
		// visited
		vector<bool > visited(N+1, false);
		// initialize
		for (vector<vector<int> >::iterator i = times.begin(); i != times.end(); ++i)
		{
			adj[(*i)[0]].push_back(make_pair((*i)[1], (*i)[2]));
		}
		dist_p[K] = make_pair(0, K);

		// dijkstra
		for (int i = 1; i < N; ++i)
		{
			// find the min dist node
			int u = K;
			int m_dist = INT_MAX;
			for (int i = 0; i < dist_p.size(); ++i)
			{
				if(dist_p[i].first < m_dist && !visited[i]){
					u = i;
					m_dist = dist_p[i].first;
				}
			}
			visited[u] = true;

			//relax
			for (int i = 0; i < adj[u].size(); ++i)
			{
				int v = adj[u][i].first;
				int distuv = adj[u][i].second;
				if(dist_p[v].first > distuv + dist_p[u].first){
					dist_p[v].first = distuv + dist_p[u].first;
					dist_p[v].second = u;
				}
			}
		}
		
		// test whether all the node has path to K
		int far = 0;
		for (int i = 1; i < N+1; ++i)
		{
			if(dist_p[i].first > far){
				far = dist_p[i].first;
			}
		}
		if(INT_MAX == far){
			return -1;
		}else{
			return far;
		}
    }
};