Submission #851233

#	Time	Username	Problem	Language	Result	Execution time	Memory
851233		vjudge1	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	282 ms	33172 KiB

commuter_pass

#include <bits/stdc++.h>
#define TASK "bus"
#define f first
#define s second

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;
typedef pair<int, ll> ill;
typedef pair<ll, int> lli;
typedef pair<ll, ll> pll;

const int MAX = 1e5 + 10;
const int MOD = 1e9 + 7;

class state
{
public:
        int v;
        ll w;
        bool cont, cur_cont;
        state() { v = w = cont = cur_cont = 0; }
        state(const int &I_v, const ll &I_w, const bool &I_cont, const bool &I_ccont)
        {
                v = I_v;
                w = I_w;
                cont = I_cont;
                cur_cont = I_ccont;
        }

        bool operator<(const state &SE) const { return w > SE.w; }
};

struct cmp
{
        bool operator()(ill FI, ill SE) { return FI.s > SE.s; }
};

int n, m, free_start, free_end, p_start, p_end;
vector<ii> e[MAX];
ll fdist[2][MAX];
priority_queue<ill, vector<ill>, cmp> qx;

void DIJKSTRA_BUILD(int start, int nt)
{
        for (int i = 1; i <= n; ++i)
                fdist[nt][i] = LLONG_MAX;
        fdist[nt][start] = 0;
        qx.push({start, 0});

        while (qx.size())
        {
                int cv = qx.top().f;
                ll cw = qx.top().s;
                qx.pop();
                if (fdist[nt][cv] < cw)
                        continue;

                for (auto itr : e[cv])
                {
                        int nv = itr.f, nxw = itr.s;
                        if (fdist[nt][nv] > cw + nxw)
                        {
                                fdist[nt][nv] = cw + nxw;
                                qx.push({nv, cw + nxw});
                        }
                }
        }
}

ll rdist[MAX][2][2];
priority_queue<state> qrx;
ll result = LLONG_MAX;

bool IN_PATH(int v1, int v2, int w)
{
        return fdist[0][v1] + fdist[1][v2] + w == fdist[0][free_end];
}

void DIJKSTRA_RUN(int z_start, int z_end)
{
        for (int i = 1; i <= n; ++i)
                for (int j = 0; j < 2; ++j)
                        rdist[i][j][0] = rdist[i][j][1] = LLONG_MAX;
        rdist[z_start][0][0] = 0;
        qrx.push(state(z_start, 0, 0, 0));
        while (qrx.size())
        {
                int cv = qrx.top().v;
                ll cw = qrx.top().w;
                bool cc1 = qrx.top().cont, cc2 = qrx.top().cur_cont;
                qrx.pop();
                if (cw > rdist[cv][cc1][cc2])
                        continue;
                if (cv == z_end)
                        break;

                for (auto itr : e[cv])
                {
                        int nv = itr.f, nxw = itr.s;
                        if (rdist[nv][cc1][0] > cw + nxw)
                        {
                                rdist[nv][cc1][0] = cw + nxw;
                                qrx.push(state(nv, cw + nxw, cc1, 0));
                        }
                        if (IN_PATH(cv, nv, nxw))
                        {
                                if (cc1 && !cc2)
                                        continue;
                                if (rdist[nv][1][1] > cw)
                                {
                                        rdist[nv][1][1] = cw;
                                        qrx.push(state(nv, cw, 1, 1));
                                }
                        }
                }
        }
        result = min({result, rdist[z_end][1][1], rdist[z_end][1][0], rdist[z_end][0][0]});
}

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

        if (fopen(TASK ".inp", "r"))
        {
                freopen(TASK ".inp", "r", stdin);
                freopen(TASK ".out", "w", stdout);
        }

        cin >> n >> m >> free_start >> free_end >> p_start >> p_end;
        while (m--)
        {
                int u1, u2, uw;
                cin >> u1 >> u2 >> uw;
                e[u1].push_back({u2, uw});
                e[u2].push_back({u1, uw});
        }

        DIJKSTRA_BUILD(free_start, 0);
        DIJKSTRA_BUILD(free_end, 1);

        DIJKSTRA_RUN(p_start, p_end);
        DIJKSTRA_RUN(p_end, p_start);
        cout << result;
}

Compilation message (stderr)

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

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