Untitled
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