SPFA以及自己踩的坑
#include <algorithm>
#include <bits/stdc++.h>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <math.h>
#include <queue>
#include <string>
using namespace std;
#define MAX 100000
int gra[105][105];//已知条件
int dis[105];//源点到其他顶点的距离
int vis[105];//标记当前顶点是否存在于队列中
void spfa(int s,int n){
dis[s]=0;//源点到自己的距离为0，在每一个最短路径题目中，初始化很重要
priority_queue<int> q;
q.push(s);
vis[s]=1;
while (!q.empty()) {
int now =q.top();
q.pop();
vis[now]=0;
//如果源点通过当前now,能与其他顶点变得更近，就修改dis的值？
for(int i=1;i<=n;++i){
//此处的顶点，是在队列中，而不是所有最小边的集合，故它也要判断是否能通过now更新距离
if(dis[i]>dis[now]+gra[now][i]){
dis[i]=dis[now]+gra[now][i];
//修改距离了不是无脑入队，要不在队列里面才入队 ...
The road of your choice, you have to go on !
粤ICP备16082171号-1
登录后发布评论
赞一个