| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 | 
|---|---|---|---|---|---|---|---|
| 525630 | somo | Travelling Merchant (CCO21_day2problem1) | C++14 | 0 ms | 0 KiB | 
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#define ll long long
#define pii pair<ll,ll>
#define F first
#define S second
using namespace std;
const int N = 200005;
ll n;
ll m;
ll in[N][4], out[N];
unordered_set<ll>f[N],b[N];
bool vis[N];
queue<ll>q;
priority_queue<pii>pq;
int main()
{
    ios::sync_with_stdio(0);
    con.tie(NULL);
    memset(vis,false,sizeof(vis));
    cin >> n >> m;
    for(ll i=1;i<=m;i++){
        ll x,y,z,w;
        cin >> x >> y >> z >> w;
        in[i][0] = x;
        in[i][1] = y;
        in[i][2] = z;
        in[i][3] = w;
        f[x].insert(i);
        b[y].insert(i);
    }
    for(ll i=1;i<=n;i++){
        if(f[i].empty()){
            q.push(i);
        }
    }
    while(q.size()){
        int cur = q.front();
        q.pop();
        out[cur] = -1;
        for(auto &i : b[cur]){
            if(vis[i]) continue;
            vis[i] = 1;
            f[in[i][0]].erase(f[in[i][0]].find(i));
            if(f[in[i][0]].empty()) q.push(in[i][0]);
        }
    }
    for(ll i=1;i<=m;i++){
        if(!vis[i]){
            pq.push({in[i][2] , i});
        }
    }
    while(pq.size()){
        pii cur = pq.top();
        q.pop();
        if(vis[cur.S]) continue;
        vis[cur.S] = 1;
        f[in[cur.S][0]].erase(f[in[cur.S][0]].find(cur.S));
        b[in[cur.S][1]].erase(b[in[cur.S][1]].find(cur.S));
        if(f[in[cur.S][0]].empty()){
            for(auto &i : b[in[cur.S][0]]){
                if(!vis[i]){
                    if(cur.F - in[i][3] > in[i][2]) pq.push({cur.F-in[i][3],i});
                }
            }
            out[in[cur.S][0]] = cur.F;
        }
    }
    for(ll i=1;i<n;i++) cout << out[i] << ' ';
    cout << out[n] << endl;
}
