下面贴下我的AC完整代码,除了上面while部分的,其余是一样的
```cpp
#include<bits/stdc++.h>
using namespace std;
struct edge
{
int to,nxt,w;
}a[500005];
int first[10005];
int visit[10005];
int top=0;
int dis[10005];
struct cmp
{
bool operator()(int x,int y)
{
return dis[x]>dis[y];
}
};
void addedge(int u,int v,int w)
{
top++;
a[top].to=v;
a[top].w=w;
a[top].nxt=first[u];
first[u]=top;
}
int main()
{
// freopen("1.in","r",stdin);
std::ios::sync_with_stdio(false);
memset(first,-1,sizeof(first));
int i,j;
int n,m,s;
cin>>n>>m>>s;
for (i=1;i<=m;i++)
{
int u,v,w;
cin>>u>>v>>w;
addedge(u,v,w);
}
for (i=1;i<=n;i++)
dis[i]=2147483647;
priority_queue<int,vector<int>,cmp>q;
dis[s]=0;
q.push(s);
while (!q.empty())
{
int u=q.top();
q.pop();
if (!visit[u])
{
visit[u]=1;
for (i=first[u];i!=-1;i=a[i].nxt)
{
int v=a[i].to;
dis[v]=min(dis[v],dis[u]+a[i].w);
q.push(v);
}
}
}
for (i=1;i<=n;i++)
cout<<dis[i]<<" ";
return 0;
}
```
by programmmmmmm @ 2018-07-20 21:04:42
dis是可以更新多次的吧。。。
by Brioche @ 2018-07-21 10:55:02
还有dijkstra不需要vis数组吧。。
by Brioche @ 2018-07-21 10:56:19
@[Brioche](/space/show?uid=61672)
没错啊,我dis都是多次更新的,dijkstra是每个点只进一次队列啊
by programmmmmmm @ 2018-07-22 10:32:11
dijkstra是每个点只会出一次队列。。。
by Brioche @ 2018-07-22 19:07:55
```cpp
while(!q.empty())
{
int u=q.top();q.pop();
for(int i=head[u];i;i=next[i])
{
int v=to[i];
if(dis[u]+w[i]<dis[v])
{
dis[v]=min(dis[u]+w[i],dis[v]);
q.push(v);
}
}
}
```
by Brioche @ 2018-07-22 19:08:57
这样写其实就可以了
by Brioche @ 2018-07-22 19:09:43
修改其实和$O(n^2)$差不多。只是查询最小值的时候用优先队列而已。。
by Brioche @ 2018-07-22 19:11:32
你的问题和这个一样[](https://www.luogu.org/discuss/show?postid=51361)
但是我看不懂
by 0xflag @ 2018-07-27 21:11:10
@[Zyffff](/space/show?uid=48530) https://www.luogu.org/discuss/show?postid=51361
by 0xflag @ 2018-07-27 21:11:28