Когда порядок обработки может изменить правильность алгоритма? Очередь очереди и приоритет ⇐ C++

[Anonymous]

Вот LeetCode Q
1976. Количество способов прибыть в пункт назначения < /p>
Вы находитесь в городе, который состоит из N перекрестков, пронумерованных от 0 до N - 1, с двунаправленными дорогами между некоторыми пересечениями. Входные данные генерируются так, что вы можете достичь любого пересечения от любого другого пересечения, и что между любыми двумя пересечениями существует не более одной дороги. Вы хотите знать, сколько способов вы можете путешествовать с перекрестка 0 к перекрестке n - 1 в кратчайшие сроки. Поскольку ответ может быть большим, вернуть его модуль 109 + 7. < /p>
Пример 1: < /p>
Input: n = 7, roads = [[0,6,7],[0,1,2],[1,2,3],[1,3,3],[6,3,3],[3,5,1],[6,5,1],[2,5,1],[0,4,5],[4,6,2]]
Output: 4
Explanation: The shortest amount of time it takes to go from intersection 0 to intersection 6 is 7 minutes.
The four ways to get there in 7 minutes are:
- 0 ➝ 6
- 0 ➝ 4 ➝ 6
- 0 ➝ 1 ➝ 2 ➝ 5 ➝ 6
- 0 ➝ 1 ➝ 3 ➝ 5 ➝ 6
< /code>
Пример 2: < /p>
Input: n = 2, roads = [[1,0,10]]
Output: 1
Explanation: There is only one way to go from intersection 0 to intersection 1, and it takes 10 minutes.
< /code>
Я могу правильно решить это, используя dijstra и очередь приоритетов. Но почему бы я не использовал очередь вместо этого? В конце концов, все приоритетное_ККЕЕ-это обрабатывать более короткие расстояния, а затем игнорируют большее расстояние на основе блока if-else. < /P>
Вот мое решение кода, приоритет_Куэуэ был прокомментирован. < /P>
class Solution {
public:

int MOD = 1e9 + 7;

int countPaths(int n, vector& roads) {
//queue
> q;
//node, timeTaken
vector ways(n, 0);
ways[0] = 1;
vector distance(n, 1e12+7);
distance[0] = 0;

queue q;

// priority_queue q;
q.push({0,0});

vector adj(n);
for(auto it: roads) {
adj[it[0]].push_back({it[1], it[2]});
adj[it[1]].push_back({it[0], it[2]});
}

while(!q.empty()) {
int node = q.front().second;
long long dist = q.front().first;
q.pop();

if(distance[node] < dist) {
continue;
}

for(auto it: adj[node]) {
int dst = it.first;
long long extraDist = it.second;

long long totalDist = dist + extraDist;

if(distance[dst] > totalDist) {
distance[dst] = totalDist;
ways[dst] = ways[node];
q.push({totalDist, dst});
}
else if(distance[dst] == totalDist) {
ways[dst] = (ways[dst] + ways[node]) % MOD;
}
else {
//do nothing.
}

}

}
int ans = ways[n - 1] % MOD;
return ans;
}
< /code>
}; < /p>
Я также прикрепляю Testcase.
Очередь дает ответ как 71 и приоритетная очередь справедливо отвечает как 166.
n = 12
Roads = = [[1,0,2348], [2,1,2852], [2,0,5200], [3,1,12480], [2,3,9628], [4,3,7367], [4,0,22195], [5,4,5668], [1,5,25515], [0,5,27863], [6,5,836], [6,0,28699] , [2,6,23499], [6,3,13871], [1,6,26351], [5,7,6229], [2,7,28892], [1,7,317 44], [3,7,19264], [6,7,5393], [2,8,31998], [8,7,3106], [3,8,22370], [8,4,1 5003], [8,6,8499], [8,5,9335], [8,9,5258], [9,2,37256], [3,9,27628], [7,9, 8364], [1,9,40108], [9,5,14593], [2,10,45922], [5,10,23259], [9,10,8666], [10,0,51122], [10,3,36294], [10,4,28927], [11,4,25190], [11,9,4929], [11, 8,10187], [11,6,18686], [2,11,42185], [11,3,32557], [1,11,45037]]
Спасибо! < /p>

Подробнее здесь: https://stackoverflow.com/questions/796 ... hm-queue-a