BinaryBoy1's blog

By BinaryBoy1, history, 6 months ago, In English,
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <cmath>
#include <map>
#include <queue>
using namespace std;
const int MAXN = 1e5 + 10;
bool flag [ MAXN ];
long long int par [ MAXN ] , alessia[ MAXN ];
vector < pair < int , int > > v[ MAXN ] ;
priority_queue <  pair <long long int , long long int > > q;
int n , m;
void Dijkstra (int st1 , int end1)
{
	q.push(make_pair(0 , st1));
	for(int i = 0 ; i < MAXN ; i++)
		alessia [ i ] = -1;
	while(true)
	{
		if(q.empty())
			break;
	    pair < int , int > p1;
		p1 = q.top();
		q.pop();
		long long int minpath = -(p1.first) , nod = p1.second;
		flag [ nod ] =  true;
		if(nod == end1)
		{
			cout << minpath << endl;
			return;
		}	
		for(int j = 0 ; j < v [ nod ].size() ; j++)
		{
			if(flag [ v [ nod ][ j ].first ] == false && (minpath + v [ nod ][ j ].second < alessia [ v [ nod ][ j ].first ]||alessia [ v [ nod ][ j ].first ] == -1))
			{
				q.push(make_pair(-(minpath + v [ nod ][ j ].second ), v [ nod ][ j ].first));
				alessia [ v [ nod ][ j ].first ] = (minpath + v [ nod ][ j ].second );
				par [ v [ nod ][ j ].first ] = nod;
			}
		}
	}
	cout << -1;
	exit(0);
}
void getpar(int a)
{
	if(par [ a ] != 0)
		getpar(par [ a ]);
	cout << a << ' ';
}
int main() {
	ios::sync_with_stdio(false) , cin.tie(0) , cout.tie(0);
	cin >> n >> m;
	for(int i = 0 ; i < m ; i++)
	{
		int a , b , c ;
		cin >> a >> b >> c;
		v [ a ].push_back(make_pair(b , c));
		v [ b ].push_back(make_pair(a , c));
	}
	
	Dijkstra (1, n);
	getpar(n);
}
 
 
 
 
  • Vote: I like it  
  • -25
  • Vote: I do not like it  

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I think the main framework of your codes is correct.

But after we take out a "node" from the priority queue, the distance of this current node to the starting point is not always equal to the "true" minimum distance. The reason is that whenever a node is "updated", we will immediately push it into the priority queue, while the "updated" distance may not be the final result.

Therefore, it is not always correct to set the "flag=true" after taking out a node from the priority queue. Instead, we usually adopt another array dis[i] to record the current "best" minimum distance to the starting point for the i-th node, and if the first node in the priority queue does not have the same distance as dis[i], we should skip this node and check the next one in the priority queue.

I think perhaps you can read the "spfa" function written in this code 1029303. Note that an array d[] is used there.