제출 #1283050

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1283050		anhphant	Commuter Pass (JOI18_commuter_pass)	C++20	0 / 100	2095 ms	29960 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second

ll N, M, S, T, U, V;
struct edge {
    ll v, w, f;
    edge() {
        v = 0;
        w = 0;
        f = 0;
    }
    edge(ll v_, ll w_, ll f_) {
        v = v_;
        w = w_;
        f = f_;
    }
};
vector<edge> GR[100007];
ll dist[100007], visited[100007];
ll DP[100007][4], DPvisited[100007][4];

int main() {
    ios_base :: sync_with_stdio(0);
    cin.tie(0); cout.tie(0); cerr.tie(0);
    if (fopen("test.inp", "r")) {
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }

    cin >> N >> M >> S >> T >> U >> V;
    for(int i = 1; i <= M; ++i) {
        ll u, v, c;
        cin >> u >> v >> c;
        GR[u].push_back(edge(v, c, 0));
        GR[v].push_back(edge(u, c, 0));
    }

    struct cmp {
        bool operator () (ll x1, ll x2) {
            return dist[x1] > dist[x2];
        }
    };

    for(int i = 0; i <= N + 3; ++i) dist[i] = 1e18;
    dist[S] = 0;
    priority_queue<ll, vector<ll>, cmp> heap;
    heap.push(S);
    while(!heap.empty()) {
        ll u = heap.top();
        heap.pop();
        if (visited[u]) continue;
        visited[u] = 1;
        for(auto tmp : GR[u]) {
            ll v = tmp.v;
            ll w = tmp.w;
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                heap.push(v);
            }
        }
    }
   // for(int i = 1; i <= N; ++i) cerr << dist[i] << " "; cerr << '\n';
    //coloring
    set<pair<ll, ll>> chosen;
    auto dfs = [&](auto&& self, ll u) -> void {
        for(auto tmp : GR[u]) {
            ll v = tmp.v;
            ll w = tmp.w;
            if (dist[v] == dist[u] - w) {
                chosen.insert({u, v});
                self(self, v);
            }
        }
    };
    dfs(dfs, T);

    for(int i = 1; i <= N; ++i) {
        for(auto& tmp : GR[i]) {
            if (chosen.count({i, tmp.v}) || chosen.count({tmp.v, i})) {
                tmp.f = 1;
            }
            if (tmp.f == 1) {
              // cerr << "f1: " << i << " " << tmp.v << '\n';
            }
        }
    }

    //calc dp U to V
    struct cmp2 {
        bool operator () (pair<ll, ll>& x1, pair<ll, ll>& x2) {
            return DP[x1.fi][x1.se] > DP[x2.fi][x2.se];
        }
    };
    priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, cmp2> heap2;
    for(int i = 0; i <= N + 2; ++i) DP[i][0] = DP[i][1] = DP[i][2] = DP[i][3] = 1e18;
    DP[U][0] = 0;
    heap2.push({U, 0});
    while(!heap2.empty()) {
        auto tmp = heap2.top();
        heap2.pop();
        ll u = tmp.fi;
        ll s = tmp.se;
        if (DPvisited[u][s]) continue;
        DPvisited[u][s] = 1;
        //cerr << u << " " << s << " " << DP[u][s] << '\n';

        for(auto tmp2 : GR[u]) {
            ll v = tmp2.v;
            ll w = tmp2.w;
            ll f = tmp2.f;

            if (s == 0) {
                if (DP[v][0] > DP[u][0] + w) {
                    DP[v][0] = DP[u][0] + w;
                    heap2.push({v, 0});
                }
                if (f == 1 && dist[u] == dist[v] + w && DP[v][1] > DP[u][0]) {
                    DP[v][1] = DP[u][0];
                    heap2.push({v, 1});
                }
                if (f == 1 && dist[u] + w == dist[v] && DP[v][2] > DP[v][0]) {
                    DP[v][2] = DP[u][0];
                    heap2.push({v, 2});
                }
            }
            if (s == 1) {
                if (f == 1 && dist[u] == dist[v] + w && DP[v][1] > DP[u][1]) {
                    DP[v][1] = DP[u][1];
                    heap2.push({v, 1});
                }
                if (DP[v][3] > DP[u][1] + w) {
                    DP[v][3] = DP[u][1] + w;
                    heap2.push({v, 3});
                }
            }
            if (s == 2) {
                if (f == 1 && dist[u] + w == dist[v] && DP[v][2] > DP[u][2]) {
                    DP[v][2] = DP[u][2];
                    heap2.push({v, 2});
                }
                if (DP[v][3] > DP[u][2] + w) {
                    DP[v][3] = DP[u][2] + w;
                    heap2.push({v, 3});
                }
            }
            if (s == 3) {
                if (DP[v][3] > DP[u][3] + w) {
                    DP[v][3] = DP[u][3] + w;
                    heap2.push({v, 3});
                }
            }
        }
    }

    cout << min({DP[V][0], DP[V][1], DP[V][2], DP[V][3]});
}

컴파일 시 표준 에러 (stderr) 메시지

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:29:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:30:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |         freopen("test.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 16
• Subtask 2: 0 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 45