Submission #850594

#	Time	Username	Problem	Language	Result	Execution time	Memory
850594		vjudge1	Commuter Pass (JOI18_commuter_pass)	C++17	31 / 100	240 ms	27484 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], rdist[MAX][2][2];
priority_queue<ill, vector<ill>, cmp> qx;
priority_queue<state> qrx;
ll result = LLONG_MAX;

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});
                        }
                }
        }
}

bool IN_PATH(int x)
{
        return fdist[0][x] + fdist[1][x] == fdist[0][free_end];
}

void DIJKSTRA_RUN(int start, int finish)
{
        while (qrx.size())
                qrx.pop();
        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[start][0][0] = 0;
        qrx.push(state(start, 0, 0, 0));
        if (IN_PATH(start))
        {
                rdist[start][0][1] = 0;
                qrx.push(state(start, 0, 0, 1));
        }

        while (qrx.size())
        {
                int cv = qrx.top().v;
                ll cw = qrx.top().w;
                bool freed = qrx.top().cont, cfree = qrx.top().cur_cont;
                qrx.pop();
                if (cw > rdist[cv][freed][cfree])
                        continue;
                if (cv == finish)
                {
                        result = min(result, cw);
                        return;
                }

                for (auto itr : e[cv])
                {
                        int nv = itr.f, nxw = itr.s;
                        ll ncw;
                        bool n_freed = freed, n_cfree;
                        if (cfree)
                        {
                                ncw = cw;
                                if (IN_PATH(nv))
                                        n_cfree = n_freed = 1;
                                else
                                {
                                        n_cfree = 0;
                                        ncw += nxw;
                                }
                        }
                        else
                        {
                                ncw = cw + nxw;
                                if (!IN_PATH(nv))
                                        n_cfree = 0;
                                else if (n_freed)
                                        n_freed = n_cfree = 0;
                                else
                                        n_cfree = 1;
                        }
                        if (rdist[nv][n_freed][n_cfree] > ncw)
                        {
                                rdist[nv][n_freed][n_cfree] = ncw;
                                qrx.push(state(nv, ncw, n_freed, n_cfree));
                        }
                }
        }
}

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:151:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  151 |                 freopen(TASK ".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:152:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  152 |                 freopen(TASK ".out", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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