萌新刚学dijkstra，52pts WA on#1#3#4,求条

NaNO2_Cabbage @ 2023-09-21 16:05:58

#include<bits/stdc++.h>
//#include<stdlib>
#define int long long 
using namespace std;

int n,m,s;
int uu,vv,ww;
vector<pair<int,int> > g[500005];
priority_queue<pair<int,int > > q;
int dis[500005],vis[500005];
int u;

inline int read(){
    int s=0,w=1;
    char ch=getchar();
    while(ch>'9'||ch<'0')w=(ch=='-'?-1:1),ch=getchar();
    while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
    return s*w;
}

inline void write(int x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
//  cout<<x<<endl;
    putchar((x%10)+'0');
}

inline void dij(int s) {
//  memset(dis,127,sizeof dis);
    for(int i=0;i<=n+1;i++)dis[i]=1e20;
//  vis[s]=1,
    dis[s]=0;
    q.push({0,s});
    while(!q.empty()) {
        u=q.top().second;
        q.pop();
        if(vis[u])continue;
        vis[u]=1;
        for(auto v:g[u]) 
            if(dis[v.first]>dis[u]+v.second) {
                dis[v.first]=dis[u]+v.second;
                if(!vis[v.first])q.push({-v.second,v.first});
            }
    }
}

signed main() {
//  scanf("%d%d%d",&n,&m,&s);
    n=read(),m=read(),s=read();
//  cout<<n<<m<<s;
    for(register int i=1; i<=m; i++) {
//      scanf("%d%d%d",&uu,&vv,&ww);
        uu=read(),vv=read(),ww=read();
        g[uu].push_back({vv,ww});
    }
    dij(s);
    for(register int i=1; i<=n; i++)write(dis[i]),putchar(' ');
}

by C6H6 @ 2023-09-21 16:17:55

if(!vis[v.first])q.push({-v.second,v.first});

改为

if(!vis[v.first])q.push({-dis[v.first],v.first});

by _XHY20180718_ @ 2023-09-21 16:18:59

#include<bits/stdc++.h>
//#include<stdlib>
#define int long long 
using namespace std;

int n,m,s;
int uu,vv,ww;
vector<pair<int,int> > g[500005];
priority_queue<pair<int,int > > q;
int dis[500005],vis[500005];
int u;

inline int read(){
    int s=0,w=1;
    char ch=getchar();
    while(ch>'9'||ch<'0')w=(ch=='-'?-1:1),ch=getchar();
    while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
    return s*w;
}

inline void write(int x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
//  cout<<x<<endl;
    putchar((x%10)+'0');
}

inline void dij(int s) {
//  memset(dis,127,sizeof dis);
    for(int i=0;i<=n+1;i++)dis[i]=1e9;
//  vis[s]=1,
    dis[s]=0;
    q.push({0,s});
    while(!q.empty()) {
        u=q.top().second;
        q.pop();
        if(vis[u])continue;
        vis[u]=1;
        for(auto v:g[u]) 
            if(dis[v.first]>dis[u]+v.second) {
                dis[v.first]=dis[u]+v.second;
                if(!vis[v.first])q.push({-dis[v.first],v.first});
            }
    }
}

signed main() {
//  scanf("%d%d%d",&n,&m,&s);
    n=read(),m=read(),s=read();
//  cout<<n<<m<<s;
    for(register int i=1; i<=m; i++) {
//      scanf("%d%d%d",&uu,&vv,&ww);
        uu=read(),vv=read(),ww=read();
        g[uu].push_back({vv,ww});
    }
    dij(s);
    for(register int i=1; i<=n; i++)write(dis[i]),putchar(' ');
}

by C6H6 @ 2023-09-21 16:19:13

@NaNO2_Cabbage

by NaNO2_Cabbage @ 2023-09-22 13:31:18

@C6H6 @XHY20180718 感谢，已过，已关注