dijkstra 36分 求调

hjy08 @ 2022-12-31 19:27:16

#include<bits/stdc++.h>
using namespace std;
int read() {
    int nn=0,mm=1;
    char ch=getchar();
    while(ch>'9'||ch<'0') {
        if(ch=='-') {
            mm=-1;
        }
        ch=getchar();
    }
    while(ch<='9'&&ch>='0') {
        nn=nn*10+ch-'0';
        ch=getchar();
    }
    return nn*mm;
}
struct bian{
    int next;
    int len;
    int to;
} a[200001];
struct dian{
    int dis;
    int i;
    bool operator <(const dian &x)const{
        return x.dis<dis;
    }
};
int dis[100001],head[100001];
bool vis[100001];
int n,m,k;
priority_queue<dian>q;
void dijkstra() {
    for(int i=1; i<=n; i++) dis[i]=INT_MAX;
    dis[k]=0;
    while(!q.empty()){
        int now=q.top().i;
        q.pop();
        if(vis[now]){
            continue;
        }
        vis[now]=1;
        for(int i=head[now];i;i=a[i].next){
            int y=a[i].to;
            if(dis[y]>dis[now]+a[i].len) {
                dis[y]=dis[now]+a[i].len;
                if(!vis[y]){
                    q.push({dis[y],y});
                }
            }

        }
    }
}
int main() {
    n=read(),m=read();
    k=read();
    for(int i=1;i<=m;i++){
        int s=read(),e=read(),len=read();
        a[i].next=head[s];
        a[i].len=len;
        a[i].to=e;
        head[s]=i;
    }
    q.push({0,k});
    dijkstra();
    for(int i=1;i<=n;i++){
        printf("%d ",dis[i]);
    }
    return 0;
}

by _XHY20180718_ @ 2022-12-31 19:41:19

@hjy08

去掉!vis[y]额。

随手改了一下，A了。

#include<bits/stdc++.h>
using namespace std;
int read() {
    int nn=0,mm=1;
    char ch=getchar();
    while(ch>'9'||ch<'0') {
        if(ch=='-') {
            mm=-1;
        }
        ch=getchar();
    }
    while(ch<='9'&&ch>='0') {
        nn=nn*10+ch-'0';
        ch=getchar();
    }
    return nn*mm;
}
struct bian{
    int next;
    int len;
    int to;
} a[200001];
struct dian{
    int dis;
    int i;
    bool operator <(const dian &x)const{
        return x.dis<dis;
    }
};
int dis[100001],head[100001];
bool vis[100001];
int n,m,k;
priority_queue<dian>q;
void dijkstra() {
    for(int i=1; i<=n; i++) dis[i]=INT_MAX;
    dis[k]=0;
    while(!q.empty()){
        int now=q.top().i;
        q.pop();
        if(vis[now]){
            continue;
        }
        vis[now]=1;
        for(int i=head[now];i;i=a[i].next){
            int y=a[i].to;
            if(dis[y]>dis[now]+a[i].len) {
                dis[y]=dis[now]+a[i].len;
                q.push({dis[y],y});
            }

        }
    }
}
int main() {
    n=read(),m=read();
    k=read();
    for(int i=1;i<=m;i++){
        int s=read(),e=read(),len=read();
        a[i].next=head[s];
        a[i].len=len;
        a[i].to=e;
        head[s]=i;
    }
    q.push({0,k});
    dijkstra();
    for(int i=1;i<=n;i++){
        printf("%d ",dis[i]);
    }
    return 0;
}

by hjy08 @ 2023-01-02 15:18:12

@xiehuiying 谢谢