Untitled

 avatar
unknown
plain_text
4 months ago
991 B
3
Indexable
class Solution {
public:
    int countPaths(int n, vector<vector<int>>& roads) {
		int minTime = 999999;
        unordered_map<int, int> mp;
		vector<pair<int, int>> node[201];
		for (auto &road : roads) {
			node[road[0]].push_back({road[1], road[2]});  // nexNode, cost
		}
		int visit[n+1] ;
        for(int i=0; i<n; i++) {
            visit[i] = 0;
        }
		queue<pair<int, int>> q;  // node, time
		q.push({0, 0});
		visit[0] = 0;
		while (!q.empty()) {
			int curNode = q.front().first;
			int curTime = q.front().second;
			if(curNode == n - 1) {
				if(curTime <= minTime) {
					minTime = curTime;
					mp[minTime]++;
				}
			}
			q.pop();
			for (auto &next : node[curNode]) {
				int nextNode = next.first;
				int nextTime = next.second;
				if(!visit[nextNode] || (curTime + nextTime < visit[nextNode])) {
					visit[nextNode] = curTime + nextTime;
					q.push({nextNode, visit[nextNode]});
				}
			}
		}
		return mp[minTime];
    }
};
Editor is loading...
Leave a Comment