제출 #1363441

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1363441		liptonek	Currents (EGOI25_currents)	C++20	100 / 100	147 ms	27268 KiB

Main

#include <bits/stdc++.h>
using namespace std;

const int INF=1e9+7;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n,m;
    cin>>n>>m;

    vector<vector<int>> adj(n);
    vector<vector<int>> rev(n);

    for(int i=0; i<m; i++)
    {
        int u,v;
        cin>>u>>v;

        adj[u].push_back(v);
        rev[v].push_back(u);
    }

    vector<int>  d0(n,INF);
    queue<int> q;

    d0[0]=0;

    q.push(0);

    while(!q.empty())
    {
        int u=q.front();
        q.pop();

        for(int v : adj[u])
        {
            if(d0[v]==INF)
            {
                d0[v]=d0[u]+1;

                q.push(v);
            }
        }
    }

    vector<int> e(n,INF);
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;

    e[n-1]=0;

    pq.push({0,n-1});

    while(!pq.empty())
    {
        int dist=pq.top().first;
        int u=pq.top().second;

        pq.pop();

        if(dist>e[u])
        {
            continue;
        }

        for(int v : rev[u])
        {
            int candidate=max(d0[v],dist+1);

            if(e[v]>candidate)
            {
                e[v]=candidate;

                pq.push({e[v],v});
            }
        }
    }

    for(int i=0; i<n-1; i++)
    {
        cout<<e[i]<<(i==n-1 ? "" : " ");
    }

    cout<<endl;

    return 0;
}

• 서브태스크 1: 0 / 0
• 서브태스크 2: 12 / 12
• 서브태스크 3: 15 / 15
• 서브태스크 4: 20 / 20
• 서브태스크 5: 29 / 29
• 서브태스크 6: 24 / 24