@[wangchuanle](/user/999799) 主播主播你的 `vis` 数组去哪了？
by endswitch @ 2024-04-20 20:36:53
```
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,M=5e5+5;
#define pi pair<int,int>
int head[N],ne[M],ver[M],w[M],tot;
int n,m,s;
int dis[N];
bool vis[N];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;
void add(int p,int q,int o){
ver[++tot]=q;
ne[tot]=head[p];
w[tot]=o;
head[p]=tot;
}
int main(){
scanf("%d%d%d",&n,&m,&s);
memset(head,-1,sizeof head);
fill(dis+1,dis+1+n,2147483647);
for(int i=1,a,b,c;i<=m;i++){
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
}
dis[s]=0;
q.push(make_pair(0,s));
while(!q.empty()){
pi tem=q.top();
q.pop();
int u=tem.second;
if(vis[u]==1){
continue;
}
vis[u]=1;
for(int i=head[u];~i;i=ne[i]){
int v=ver[i];
if(dis[v]>dis[u]+w[i]){
dis[v]=dis[u]+w[i];
q.push(make_pair(dis[v],v));
}
}
}
for(int i=1;i<=n;i++){
printf("%d ",dis[i]);
}
return 0;
}
```
想不到哪卡了（我太蒻了），可以对着我的改一改
by queenbee @ 2024-04-20 20:37:05
@[endswitch](/user/773915)
试过了，好像加了还T
by queenbee @ 2024-04-20 20:39:32
@[queenbee](/user/789564) 你真的试了吗，为什么我的改的过了？
```cpp
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll dis[200005];
typedef pair<ll,ll> P;
ll n,m,s,u,v,w;
bool vis[200005];
struct data{ll to,w;};
vector<data>head[200005];
int main()
{
scanf("%lld%lld%lld",&n,&m,&s);
for(int i=1;i<=m;i++)
{
scanf("%lld%lld%lld",&u,&v,&w);
head[u].push_back((data){v,w});
}
priority_queue<P,vector<P>,greater<P> >Q;
memset(dis,127,sizeof dis);
dis[s]=0;
Q.push(P(0,s));
while(Q.size())
{
P p=Q.top();Q.pop();
int u=p.second;
if(vis[u] == true) continue;
vis[u] = true;
for(int i=0;i<head[u].size();i++)
{
int to=head[u][i].to,w=head[u][i].w;
if(dis[to]>dis[u]+w)
{
dis[to]=dis[u]+w;
Q.push(P(dis[to],to));
}
}
}
for(int i=1;i<=n;i++)
printf("%lld ",dis[i]);
return 0;
}
```
by endswitch @ 2024-04-20 20:43:16
@[wangchuanle](/user/999799)
by endswitch @ 2024-04-20 20:43:24
@[endswitch](/user/773915)
```
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll dis[200005];
bool vis[200005];
typedef pair<ll,ll> P;
ll n,m,s,u,v,w;
struct data{ll to,w;};
vector<data>head[200005];
int main()
{
scanf("%lld%lld%lld",&n,&m,&s);
for(int i=1;i<=m;i++)
{
scanf("%lld%lld%lld",&u,&v,&w);
head[u].push_back((data){v,w});
}
priority_queue<P,vector<P>,greater<P> >Q;
memset(dis,127,sizeof dis);
dis[s]=0;
Q.push(P(0,s));
while(Q.size())
{
P p=Q.top();Q.pop();
int u=p.second;
if(vis[u]==1){
continue;
}
for(int i=0;i<head[u].size();i++)
{
int to=head[u][i].to,w=head[u][i].w;
if(dis[to]>dis[u]+w)
{
dis[to]=dis[u]+w;
Q.push(make_pair(dis[to],to));
}
}
}
for(int i=1;i<=n;i++)
printf("%lld ",dis[i]);
return 0;
}
```
by queenbee @ 2024-04-20 20:44:05
```cpp
if(vis[u] == true) continue;
vis[u] = true;
```
加了这两行。
by endswitch @ 2024-04-20 20:44:12
@[endswitch](/user/773915)
我加少了（捂脸）
by queenbee @ 2024-04-20 20:44:38
@[queenbee](/user/789564) 遍历完点 $u$ 则 $vis_u \to true$。
by endswitch @ 2024-04-20 20:45:14
@[endswitch](/user/773915)
没给vis赋1，根本不执行if :(
by queenbee @ 2024-04-20 20:45:38