@[jimmy2016](/space/show?uid=30725) err，你就用SPFA吧QwQ
by disangan233 @ 2018-07-19 10:05:20
@[jimmy2016](/space/show?uid=30725) 你这个是优先队列优化spfa吧。。。
dijkstra每个点只会进一次队
by 星小雨 @ 2018-07-19 10:11:34
什么意思？我这里进队了多次吗
by 打脸不疼 @ 2018-07-19 11:04:07
```cpp
#include <bits/stdc++.h>
#define inf 0x7fffffff
using namespace std;
struct ps
{
int id;
int dist;
bool operator > (const ps& n) const{
return dist<n.dist;
}
bool operator < (const ps& n) const{
return dist>n.dist;
}
};
struct E
{
int to;
int w;
};
priority_queue <ps> points;
int n,e,dis[20005],yd;
vector <E> GE[20005];
bool used[20005];
int main()
{
cin>>n>>e>>yd;
for(int i=1;i<=n;i++)
{
if(i!=yd)
{
dis[i]=inf;
}
}
for(int i=1;i<=e;i++)
{
int s,o,w;
E t;
cin>>s>>o>>w;
t.to=o;
t.w=w;
GE[s].push_back(t);
}
ps Y;
Y.id=yd;
Y.dist=0;
points.push(Y);
while(!points.empty())
{
ps t=points.top();
points.pop();
int p=t.id;
if(!used[p])
{
for(int i=0;i<GE[p].size();i++)
{
E et=GE[p][i];
if(dis[et.to]>dis[p]+et.w&&!used[et.to])
{
dis[et.to]=dis[p]+et.w;
ps in;
in.id=et.to;
in.dist=dis[et.to];
points.push(in);
}
}
}
used[p]=1;
}
for(int i=1;i<=n;i++)
{
cout<<dis[i]<<' ';
}
return 0;
}
```
by Barry_Wang @ 2018-07-19 11:25:51