非dfs解法,60分,有兴趣的巨佬可以看看QAQ
查看原帖
非dfs解法,60分,有兴趣的巨佬可以看看QAQ
418900
像晚风楼主2021/7/24 19:44
#include<bits/stdc++.h>
using namespace std;
const int inq=0x3f3f3f,inf=1e5+5;
int n,m,cnt,head[inf],dis[inf],vis[inf],ans[inf];
struct node{
    int next,to;
}e[inf*2];

struct edge{
    int d,x;
   bool operator<(const edge&r)const{
       return d>r.d;
   }
};
priority_queue<edge>q;
void add(int x,int y)
{
    e[++cnt]={head[x],y};
    head[x]=cnt;
}

void dijkstra(int x)
{
    memset(vis,0,sizeof(vis));
    q.push((edge){dis[x],x});
    while(!q.empty())
    {
        edge u=q.top();
        q.pop();
        int x=u.x;
        if(vis[x])continue;
        vis[x]=1;
        for(int i=head[x];i;i=e[i].next)
        {
            int to=e[i].to;

            if(dis[to]<dis[x])
            {
                dis[to]=dis[x];
                if(!vis[to])
                    q.push((edge){dis[to],to});
            }
        }
    }
}
int main()
{
    cin>>n>>m;
    int x,y;
    for(int i=1;i<=n;i++)
       dis[i]=i;
    for(int i=1;i<=n;i++)
        cin>>x>>y,add(y,x);
    for(int i=n;i>0;i--)
        dijkstra(i);
    for(int i=1;i<=n;i++)
        cout<<dis[i]<<" ";
    return 0;
}
2021/7/24 19:44
加载中...