为什么只过了最后一个点！

Director_Ni @ 2023-10-18 21:51:42

#include <bits/stdc++.h>
using namespace std;
struct EDGE {int v,y;};
vector<EDGE> e[1000009];int d[1000009];
set<pair<int,int>>q;
int main()
{
    int n,m,s,u1,v1,w1;
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<=m;++i){
        scanf("%d%d%d",&u1,&v1,&w1);
        EDGE t;
        t.y=v1;t.v=w1;
        e[u1].push_back(t);
    }
    memset(d,127,sizeof(d));
    d[s]=0;q.clear();
    for(int i=1;i<=n;++i){
        q.insert(make_pair(d[i],i));
    }
    for(;!q.empty();){
        int x=q.begin()->second;

        if(x==n||d[x]>1<<30)
            break;
        q.erase(q.begin());
        for(auto i:e[x]){
            if(d[x]+i.v<d[i.y]){
                q.erase(make_pair(d[i.v],i.y));
                d[i.y]=d[x]+i.v;
                q.insert(make_pair(d[i.v],i.y));
            }
        }
            }
        for(int i=1;i<=n;++i){
            cout<<d[i]<<" ";
        }
    return 0;
}

by Fdjo @ 2023-10-20 20:20:42

#include <bits/stdc++.h>
using namespace std;
struct EDGE {int v,y;};
vector<EDGE> e[1000009];int d[1000009];
bool vis[100005];
set<pair<int,int>>q;
int main()
{
    int n,m,s,u1,v1,w1;
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<=m;++i){
        scanf("%d%d%d",&u1,&v1,&w1);
        EDGE t;
        t.y=v1;t.v=w1;
        e[u1].push_back(t);
    }
    for (int i = 1;i <= n;i++)d[i] = 0x7fffffff;
    d[s]=0;
    q.insert({0,s});
    for(;!q.empty();){
        int a=q.begin()->second;
        int b = q.begin()->first;
        q.erase(q.begin());
        if (vis[a] == 1)continue;
        vis[a] = 1;
        for(auto i:e[a]){
            if(d[a]+i.v<d[i.y]){
                d[i.y]=d[a]+i.v;
                if (vis[i.y] == 0)q.insert(make_pair(d[i.y],i.y));
            }
        }
            }
        for(int i=1;i<=n;++i){
            cout<<d[i]<<" ";
        }
    return 0;
}

要用vis数组标记是否去过点，去过就不能再去第二次，还有一些细节在我改的代码里，下次记得悬关