求助

wangft @ 2024-05-20 23:35:22

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int n,m,st;
struct node{
    int n;
    int l;
    int b;
    bool operator<(const node&b)const
    {return l>b.l;}
};
priority_queue<node>q;
vector<node>a[2000000];
node dp[2000000];
int main(){
    int i,j,k,p;
    node x,y;
    cin>>n>>m>>st;
    for(i=1;i<=m;i++){
        cin>>x.n>>y.n>>x.l;
        y.l=x.l;
        a[x.n].push_back(y);
        a[y.n].push_back(x); 
      }
    for(i=1;i<=n;i++)
    dp[i].l=-1;
    dp[st].b=0;
    y.l=0; y.n=st; y.b=0;
    q.push(y);
    while(!q.empty()){
        x=q.top();
        q.pop();
        if(dp[x.n].l==-1){
            dp[x.n]=x;
            for(i=0;i<a[x.n].size();i++){
                y.l=a[x.n][i].l+x.l;
                y.n=a[x.n][i].n;
                y.b=x.n;
                q.push(y); 
            }
        }
    }
    for(i=1;i<=n;i++)
    cout<<dp[i].l<<" ";
  }

by mbrc123 @ 2024-05-29 11:21:25

这是有向图，存图的时候不要存两边，把第二个存的地方注释掉就可以了

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int n, m, st;
struct node{
    int n;
    int l;
    int b;
    bool operator<(const node & b)const{ return l > b.l; }
};
priority_queue<node>q;
vector<node>a[2000000];
node dp[2000000];
int main ( ){
    int i, j, k, p;
    node x, y;
    cin >> n >> m >> st;
    for (i = 1; i <= m; i++){
        cin >> x.n >> y.n >> x.l;
        y.l = x.l;
        a[x.n].push_back (y);
        // a[y.n].push_back (x);
    }
    for (i = 1; i <= n; i++)
        dp[i].l = -1;
    dp[st].b = 0;
    y.l = 0; y.n = st; y.b = 0;
    q.push (y);
    while (!q.empty ( )){
        x = q.top ( );
        q.pop ( );
        if (dp[x.n].l == -1){
            dp[x.n] = x;
            for (i = 0; i < a[x.n].size ( ); i++){
                y.l = a[x.n][i].l + x.l;
                y.n = a[x.n][i].n;
                y.b = x.n;
                q.push (y);
            }
        }
    }
    for (i = 1; i <= n; i++)
        cout << dp[i].l << " ";
}