@[毕沁露](/space/show?uid=37124)
说实话,本蒟蒻并不是很喜欢链式前向星(请不要吐槽),我喜欢STL版本的.
附上代码,希望能有用。
```cpp
#include<iostream>
#include<map>
#include<vector>
#include<queue>
using namespace std;
#define maxn 500000+1
#define INF 2147483647
vector<pair<int,int> >vec[maxn];
queue<int>que;
bool inq[maxn];
int n,m;
int d[maxn];
int x,y,z;
int s,t;
inline void init()
{
//for(int i=0;i<maxn;i++)vec[i].clear();
//for(int i=0;i<maxn;i++)inq[i]=0;
for(int i=0;i<maxn;i++)d[i]=INF;
//while(!que.empty())que.pop();
}
int main()
{
ios::sync_with_stdio(false);
cin>>n>>m>>s;
init();
for(int i=0;i<m;i++)
{
cin>>x>>y>>z;
vec[x].push_back(make_pair(y,z));
}
//cin>>s>>t;
que.push(s);d[s]=0;inq[s]=1;
while(!que.empty())
{
int now = que.front();que.pop();inq[now]=0;
for(int i=0;i<vec[now].size();i++)
{
int v=vec[now][i].first;
if(d[v]>d[now]+vec[now][i].second)
{
d[v]=d[now]+vec[now][i].second;
if(inq[v])continue;
inq[v]=1;
que.push(v);
}
}
}
//cout<<d[s];
for(t=1;t<n;t++)cout<<d[t]<<' ';
cout<<d[n];
return 0;
}//大佬们勿喷
```
by Michael123456 @ 2018-07-22 13:28:40
em 不过谢谢啦 还有没有大佬帮忙啊QWQ
by _bql @ 2018-07-22 13:31:38
找到问题了qwq
for完后要把vis取消掉
```cpp
void spfa()
{
for(i=1;i<=n;i++) dis[i]=inf;
dis[b]=0;
q.push(b),vis[b]=1;
while(!q.empty())
{
int begin=q.front();
q.pop();
for(i=head[begin];i;i=edge[i].next)
{
if(dis[edge[i].to]>dis[begin]+edge[i].dis)
{
dis[edge[i].to]=dis[begin]+edge[i].dis;
if(!vis[edge[i].to])
{
vis[edge[i].to]=1;
q.push(edge[i].to);
}
}
}
/***********************/
vis[begin]=0;
/***********************/
}
}
```
已经用注释标出@[毕沁露](/space/show?uid=37124)
by codesonic @ 2018-07-22 13:43:16
哇 谢谢大佬 @[codesonic](/space/show?uid=45443) Orz Orz
by _bql @ 2018-07-22 13:52:03
已经AC谢谢大佬
by _bql @ 2018-07-22 13:53:35