제출 #540998

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
540998		LittleCube	Olympic Bus (JOI20_ho_t4)	C++14	100 / 100	719 ms	3804 KiB

ho_t4

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
using namespace std;

ll N, M, w[50005], d[50005], ans = 1e18;
pll edge[50005];
bool recalcto[50005], recalcback[50005];
vector<ll> to, torev, back, backrev, recalctodis, recalcbackdis;
vector<int> tofrom, backfrom, tmp;
vector<int> E[205], rE[205];

pll get_edge(int id, int u)
{
    if (edge[id].F == u)
        return pll{edge[id].S, w[id]};
    else
        return pll{edge[id].F, w[id]};
}

void dijkstra(int begin, int N, vector<ll> &dis, vector<int> &from, vector<int> E[])
{
    dis = vector<ll>(N + 1, 1e18);
    dis[begin] = 0;
    from.resize(N + 1);
    priority_queue<pll, vector<pll>, greater<pll>> pq;
    pq.push({0, begin});
    while (!pq.empty())
    {
        auto [d, u] = pq.top();
        pq.pop();
        if (d > dis[u])
            continue;
        for (auto id : E[u])
        {
            auto [v, w] = get_edge(id, u);
            if (dis[v] > dis[u] + w)
            {
                dis[v] = dis[u] + w;
                pq.push({dis[v], v});
                from[v] = id;
            }
        }
    }
}

signed main()
{
    cin >> N >> M;
    for (int i = 1; i <= M; i++)
    {
        ll U, V, C, D;
        cin >> U >> V >> C >> D;
        edge[i] = {U, V};
        w[i] = C;
        d[i] = D;
        E[U].emplace_back(i);
        rE[V].emplace_back(i);
    }
    dijkstra(N, N, torev, tmp, rE);
    dijkstra(1, N, to, tofrom, E);
    dijkstra(1, N, backrev, tmp, rE);
    dijkstra(N, N, back, backfrom, E);
    //for (int i = 1; i <= N; i++)
    //    cout << to[i] << " \n"[i == N];
    //for (int i = 1; i <= N; i++)
    //    cout << back[i] << " \n"[i == N];
    if (to[N] < 1e18)
    {
        int cur = N;
        while (cur != 1)
        {
            int id = tofrom[cur];
            recalcto[id] = 1;
            cur = get_edge(id, cur).F;
        }
    }
    if (back[1] < 1e18)
    {
        int cur = 1;
        while (cur != N)
        {
            int id = backfrom[cur];
            recalcback[id] = 1;
            cur = get_edge(id, cur).F;
        }
    }
    ans = to[N] + back[1];
    //cerr << ans << '\n';
    for (int i = 1; i <= M; i++)
    {
        //cerr << i << " = ";
        ll res = d[i];
        if (recalcto[i])
        {
            //cout << " recalcto ";
            tie(edge[M + 1], w[M + 1]) = tie(edge[i], w[i]);
            w[i] = 1e18;
            E[edge[M + 1].S].emplace_back(M + 1);

            dijkstra(1, N, recalctodis, tmp, E);

            E[edge[M + 1].S].pop_back();
            tie(edge[i], w[i]) = tie(edge[M + 1], w[M + 1]);

            res += recalctodis[N];
        }
        else
            res += min(to[N], to[edge[i].S] + w[i] + torev[edge[i].F]);
        //cerr << res << " ";
        if (recalcback[i])
        {
            //cout << " recalcback ";
            tie(edge[M + 1], w[M + 1]) = tie(edge[i], w[i]);
            w[i] = 1e18;
            E[edge[M + 1].S].emplace_back(M + 1);

            dijkstra(N, N, recalcbackdis, tmp, E);

            E[edge[M + 1].S].pop_back();
            tie(edge[i], w[i]) = tie(edge[M + 1], w[M + 1]);

            res += recalcbackdis[1];
        }
        else
            res += min(back[1], back[edge[i].S] + w[i] + backrev[edge[i].F]);
        //cerr << res << "\n";
        ans = min(ans, res);
    }
    cout << (ans >= 1e18 ? -1 : ans) << '\n';
}

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

ho_t4.cpp: In function 'void dijkstra(int, int, std::vector<long long int>&, std::vector<int>&, std::vector<int>*)':
ho_t4.cpp:33:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   33 |         auto [d, u] = pq.top();
      |              ^
ho_t4.cpp:39:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   39 |             auto [v, w] = get_edge(id, u);
      |                  ^

• Subtask 1: 5 / 5
• Subtask 2: 11 / 11
• Subtask 3: 21 / 21
• Subtask 4: 63 / 63