希望更丰富的展现?使用Markdown
by rEdWhitE_uMbrElla @ 2018-11-28 23:22:19
```cpp
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<vector>
const int MN=10010;
using namespace std;
int dis[MN];
bool in[MN];
int n,m,s;
struct Edge {
int from,to,l;
Edge(int from=0,int to=0,int l=0):from(from),to(to),l(l) {};
} ;
vector<Edge> G[MN];
void SPFA(int ss) {
queue<int> q;
for(int i=1; i<=n; i++)dis[i]=2147483647;
memset(in,false,sizeof(in));
q.push(ss);
dis[ss]=0;
in[ss]=true;
while(!q.empty()) {
int u=q.front();
q.pop();
in[u]=false;
for(int unsigned i=0; i<G[u].size(); i++) {
int v=G[u][i].to;
if(dis[v]>dis[u]+G[u][i].l) {
dis[v]=dis[u]+G[u][i].l;
if(!in[i]) {
in[i]=true;
q.push(v);
}
}
}
}
}
int main() {
cin>>n>>m>>s;
for(int i=1; i<=n; i++)G[i].clear();
for(int i=1; i<=m; i++) {
int a,b,l;
cin>>a>>b>>l;
G[a].push_back(Edge(a,b,l));
}
SPFA(s);
for(int i=1; i<=n; i++) {
cout<<dis[i]<<" ";
}
return 0;
}
```
by w1049 @ 2018-11-28 23:22:25
终于发现问题了。。。。
```cpp
if(!in[i]) {
in[i]=true;
q.push(v);
}
```
这里出了毛病。。。
by w1049 @ 2018-11-28 23:25:42
用dijkstra吧,SPFA已经死了
by NaCly_Fish @ 2018-11-29 00:02:51
@[w1049344862](/space/show?uid=149392) 你在某QQ群问的时候我@你了
by yizimi远欣 @ 2018-11-29 00:36:26
就是in[v]的问题
by yizimi远欣 @ 2018-11-29 00:36:53