麻烦帮忙看一下 这个代码里面核心算法那一块具体是怎么实现的啊,蒙逼了,研究半天没有思路。好像是有问题吧。
谢谢了
#include
#include
#include
#include
#define FIN "dijkstra.in"
#define FOUT "dijkstra.out"
#define oo ((1LL<<31)-1)//近似无限大
#define MAXN 50005
using namespace std;
int nodes,//节点的数量
edges;//边的数量
vector > Graph[ MAXN ];
int distMin[ MAXN ];
queue Queue;
bitset inQueue;
void readData() {
int x,
y,
cost;
freopen(FIN, "r", stdin);
scanf("%d %d", &nodes, &edges);
while(edges--){
scanf("%d %d %d", &x, &y, &cost);
Graph[ x ].push_back({y,cost});
}
fclose( stdin );
};
void Dijkstra() {
for(int i = 2; i <= nodes; i++) distMin[ i ] = oo;//将distMin[2]之后的所有存在元素全部置为oo
distMin[ 1 ] = 0;
Queue.push( 1 );
inQueue[ 1 ] = true;
while( !Queue.empty() ) {
int node = Queue.front();//访问首结点
Queue.pop();
inQueue[ node ] = false;
for(auto it : Graph[ node ]) {//first为目的节点,second为权值
if(distMin[ it.first ] > distMin[ node ] + it.second) {
distMin[ it.first ] = distMin[ node ] + it.second;
if(!inQueue[ it.first ]) {
Queue.push( it.first );
inQueue[ it.first ] = true;
}
}
}
}
};
void writeData() {
freopen(FOUT, "w", stdout);
for(int i = 2; i <= nodes; i++)
printf("%d ", (distMin[ i ] < oo ? distMin[ i ] : 0));
fclose( stdout );
};
int main() {
readData();
Dijkstra();
writeData();
return(0);
};