52pts求助

P4779 【模板】单源最短路径(标准版)

xdd5689 @ 2023-07-19 21:00:38

rt,代码如下

#include <bits/stdc++.h>
#define l long long
using namespace std;
struct xdd
{
    l u,v,w;
};
vector<xdd> s;
vector<l> a[100006];
l n,m,p,maxn,ans[100006],dis[100006];
priority_queue<pair<l,l> > q;
bool b[100006];
l xxx()
{
    if(q.empty()) return 0;
    l h=q.top().second;
    q.pop();
    return h;
}
void dfs(l st)
{

    if(st==0)
    {
        return ;
    }    
    if(b[st]==true) return ;
    b[st]=true;
    for(l i=0;i<a[st].size();i++)
    {
        l p=s[a[st][i]].v;
        if(!b[p])
        {
            if(dis[p]>dis[st]+s[a[st][i]].w)
            {
                dis[p]=dis[st]+s[a[st][i]].w;
                q.push(make_pair(-dis[p],p));
            }

        }
    }
    dfs(xxx());
}
void mian()
{
    cin>>n>>m>>p;
    for(l i=1;i<=m;i++)
    {
        l x,y,z;
        cin>>x>>y>>z;
        xdd e;
        e.u=x,e.v=y,e.w=z;
        s.push_back(e);
    }
    for(l i=0;i<m;i++)
    {
        a[s[i].u].push_back(i);
    }
    for(l i=1;i<=n;i++)
    {
        dis[i]=pow(2,31)-1;
    }
    dis[p]=0;
    //q.push(make_pair(-dis[p],p));
    //q.pop();
    dfs(p);
    for(l i=1;i<=n;i++) printf("%lld ",dis[i]);
}
int main()
{
    mian();
    return 0;
}

by lxyt_415x @ 2023-08-09 21:05:46

同问


|