我自己基于BFS造出了一个类似SPFA的最短路径算法,完全是搞着玩的,大伙不要在意,但是我有几个问题希望各位求教:
下面是我的代码。
//exam name:A New Shortest Path Way
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
struct edge{
int next,w;
};
const int MAXN=10005;
const int INF=0x3f3f3f3f;
vector<edge> g[MAXN];
queue<int> q;
int n,m,st;
int dis[MAXN];
signed main(){
memset(dis,0x3f,sizeof(dis));
cin>>n>>m>>st;
for(int i=1,u,v,w;i<=m;i++){
cin>>u>>v>>w;
g[u].push_back((edge){v,w});
}
q.push(st);dis[st]=0;
while(!q.empty()){
int u=q.front();q.pop();
for(int i=0;i<g[u].size();i++){
int v=g[u][i].next,w=g[u][i].w;
if(dis[u]+w<dis[v]){
dis[v]=dis[u]+w;
q.push(v);
}
}
}
for(int i=1;i<=n;i++){
if(dis[i]==INF) cout<<0x7fffffff<<" ";
else cout<<dis[i]<<" ";
}
return 0;
}