Submission #393537

#	Time	Username	Problem	Language	Result	Execution time	Memory
393537		nohaxjustsoflo	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	854 ms	56872 KiB

commuter_pass

#include <bits/stdc++.h>
typedef long long ll;

using namespace std;
const int mxN = 1e5+5;
const int mxM = 2e5+5;

struct edge
{
    int u, v;
    ll c;
    int rev;
};

vector<int> out[mxN];
vector<int> in[mxN];
vector<int> new_out[mxN];
vector<int> new_in[mxN];
edge edges[2*mxM];
ll best[mxN];
bool ok[mxN]; ///vertices on shortest path
bool done[mxN];
bool cut[2*mxM];

bool fix(int i, int t)
{
    if(i == t) return true;
    if(done[i]) return ok[i];
    done[i] = true;
    for(int e : out[i])
    {
        int j = edges[e].v;
        if(cut[e]) continue;
        if(fix(j, t))
        {
            ok[i]=1;
            new_out[i].push_back(e);
            new_in[j].push_back(edges[e].rev);
        }
    }
    return ok[i];
}

/// node, used, using, direction
ll dp[mxN][2][2][2];

struct pos
{
    int i, used, cur, dir;
    bool operator<(const pos& p) const
    {
        return i < p.i;
    }
};

ll solve(int u, int v)
{
    for(int i = 0; i < mxN; i++)
        for(int j = 0; j < 2; j++)
            for(int k = 0; k < 2; k++)
                dp[i][j][k][0] = dp[i][j][k][1] = 1e18;

    ll ans = 1e18;
    dp[u][0][0][0] = 0;
    priority_queue<pair<ll, pos>> q;
    q.push({0, {u, 0, 0, 0}});
    while(!q.empty())
    {
        auto par = q.top(); q.pop();
        pos p = par.second;
        int i = p.i;
        ll cost = -par.first;
        if(cost > dp[p.i][p.used][p.cur][p.dir]) continue;
        if(i == v)
        {
            ans = min(ans, cost);
            continue;
        }
        if(!p.used)
        {
            if(!p.cur || !p.dir)
            {
                for(auto e : new_out[i]) ///kreni u 0 dir
                {
                    int j = edges[e].v;
                    if(cost < dp[j][0][1][0])
                    {
                        dp[j][0][1][0] = cost;
                        q.push({-cost, {j, 0, 1, 0}});
                    }
                }
            }
            if(!p.cur || p.dir)
            {
                for(auto e : new_in[i]) ///kreni u 1 dir
                {
                    int j = edges[e].v;
                    if(cost < dp[j][0][1][1])
                    {
                        dp[j][0][1][1] = cost;
                        q.push({-cost, {j, 0, 1, 1}});
                    }
                }
            }
            if(p.cur)
            {
                for(auto e : out[i]) ///canceluj
                {
                    int j = edges[e].v;
                    if(cost + edges[e].c < dp[j][1][0][0])
                    {
                        dp[j][1][0][0] = cost + edges[e].c;
                        q.push({-dp[j][1][0][0], {j,1,0,0}});
                    }
                }
            }
            else
            {
                for(auto e : out[i]) ///klasicno samo nastavi !used
                {
                    int j = edges[e].v;
                    if(cost + edges[e].c < dp[j][0][0][0])
                    {
                        dp[j][0][0][0] = cost + edges[e].c;
                        q.push({-dp[j][0][0][0], {j,0,0,0}});
                    }
                }
            }
        }
        else
        {
            for(auto e : out[i]) ///klasicno samo nastavi used
            {
                int j = edges[e].v;
                if(cost + edges[e].c < dp[j][1][0][0])
                {
                    dp[j][1][0][0] = cost + edges[e].c;
                    q.push({-dp[j][1][0][0], {j,1,0,0}});
                }
            }
        }
    }
    return ans;
}

int main()
{
    for(int i = 0; i < mxN; i++) best[i] = 1e18;
    int n, m;
    cin >> n >> m;
    int s, t, U, V;
    cin >> s >> t >> U >> V;
    for(int i = 0; i < m; i++)
    {
        int u, v; ll c; cin >> u >> v >> c;
        edges[i*2] = {u,v,c,i*2+1};
        edges[i*2+1] = {v,u,c,i*2};
        out[u].push_back(i*2);
        in[u].push_back(i*2+1);
        out[v].push_back(i*2+1);
        in[v].push_back(i*2);
    }
    best[s] = 0;
    ///cost, to, edge
    priority_queue<pair<ll, int>> q;
    q.push({0, s});
    while(!q.empty())
    {
        auto cur = q.top(); q.pop();
        int i = cur.second;
        int cost = -cur.first;
        if(cost > best[i]) continue;
        for(auto e : in[i])
        {
            int u = edges[e].u, v = i;
            ll c = edges[e].c;
            if(best[u] + c > best[v]) cut[e] = true;
        }
        for(auto e : out[i])
        {
            int u = i, v = edges[e].v;
            ll c = edges[e].c;
            if(best[u] + c < best[v])
            {
                best[v] = best[u] + c;
                q.push({-best[v], v});
            }
        }
    }
    fix(s, t);
    /*for(int i = 1; i <= n; i++)
    {
        cout << "node " << i << "\n";
        for(int e : new_out[i])
        {
            cout << edges[e].c << " ";
        }
        cout << "\n";
    }
    cout << "*********************************\n";
    for(int i = 1; i <= n; i++)
    {
        cout << "node " << i << "\n";
        for(int e : new_in[i])
        {
            cout << edges[e].u << edges[e].v << " ";
        }
        cout << "\n";
    }
    cout<<"\n\n";*/
    cout << solve(U, V);
}
/*
6 6
1 6
1 4
1 2 1
2 3 1
3 5 1
2 4 3
4 5 2
6 5 1

4 4
1 4
0 0
1 2 1
1 3 1
2 4 1
3 4 1
*/

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