非常好代码，使我#3T爆

wangchuanle @ 2024-04-20 20:30:13

#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;
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;
        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:36:53

@wangchuanle 主播主播你的 vis 数组去哪了？

by queenbee @ 2024-04-20 20:37:05

#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:39:32

@endswitch 试过了，好像加了还T

by endswitch @ 2024-04-20 20:43:16

@queenbee 你真的试了吗，为什么我的改的过了？

#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:24

@wangchuanle

by queenbee @ 2024-04-20 20:44:05

@endswitch

#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 endswitch @ 2024-04-20 20:44:12

if(vis[u] == true) continue;
vis[u] = true;

加了这两行。

by queenbee @ 2024-04-20 20:44:38

@endswitch 我加少了（捂脸）

by endswitch @ 2024-04-20 20:45:14

@queenbee 遍历完点 u 则 vis_u \to true。

by queenbee @ 2024-04-20 20:45:38

@endswitch 没给vis赋1，根本不执行if :(