Submission #233746

#	Time	Username	Problem	Language	Result	Execution time	Memory
233746		Coroian_David	Commuter Pass (JOI18_commuter_pass)	C++11	100 / 100	656 ms	23940 KiB

commuter_pass

//#include <bits/stdc++.h>
#include <algorithm>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <queue>
#include <set>
#include <string>
#include <vector>


#define MAX_N 100000

#define xx first
#define yy second

using namespace std;

typedef long long lint;

//ifstream cin("01-10.txt");
//ofstream cout("out.txt");

const lint sqrInf = (1e18) - 1;

lint rez;
int n, m;
int s, t;
int u, v;

vector <pair<int, int>> g[MAX_N + 1];

void add(int a, int b, int c)
{
    g[a].push_back({b, c});
}

int viz[MAX_N + 1][4];
lint dist[MAX_N + 1][4];
lint dp[MAX_N + 1][4];
int vi[MAX_N + 1][4];

priority_queue <pair<lint, int>, vector<pair<lint, int>>, greater<pair<lint, int>>> q;

struct elem
{
    lint d;
    int nod, x;
};

void readFile()
{
    cin >> n >> m;
    cin >> s >> t;
    cin >> u >> v;

    for(int i = 1; i <= m; i ++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
        add(b, a, c);
    }
}

void distra(int x, int cr)
{
    while(q.size() > 0)
        q.pop();

    for(int i = 1; i <= n; i ++)
        dist[i][cr] = sqrInf;

    dist[x][cr] = 0;
    q.push({0, x});

    while(q.size() > 0)
    {
        int a = q.top().yy;
        q.pop();

        if(viz[a][cr] == 0)
        {
            viz[a][cr] = 1;
            for(auto u : g[a])
            {
                if(dist[a][cr] + u.yy < dist[u.xx][cr])
                {
                    dist[u.xx][cr] = dist[a][cr] + u.yy;
                    q.push({dist[u.xx][cr], u.xx});
                }
            }
        }
    }
}

int okEdge(int a, int b, int c)
{
    if(dist[a][0] + dist[b][1] + c == dist[t][0])
        return 1;

    if(dist[a][1] + dist[b][0] + c == dist[t][0])
        return 1;

    return 0;
}

bool verif(int a, int b, int cr)
{
    return (dist[a][cr - 1] > dist[b][cr - 1]);
}

void getDp()
{
    auto cmp = [](elem x, elem y) {return (x.d > y.d); };

    std::priority_queue<elem, std::vector<elem>, decltype(cmp)> q(cmp);

    while(q.size() > 0)
        q.pop();

    for(int i = 1; i <= n; i ++)
    {
        for(int j = 0; j <= 3; j ++)
            dp[i][j] = sqrInf;
    }

    dp[u][0] = 0;
    q.push({0, u, 0});

    while(q.size() > 0)
    {
        int a = q.top().nod;
        int cr = q.top().x;
        q.pop();

        if(vi[a][cr] == 0)
        {
            vi[a][cr] = 1;

            if(cr == 0 || cr == 1 || cr == 2 || cr == 3)
            {
                ///0-0 and 3-3 and 1-3 and 2-3
                int w = ((cr == 1 || cr == 2) ? 3 : cr);
                for(auto u : g[a])
                {
                    if(dp[a][cr] + u.yy < dp[u.xx][w])
                    {
                        dp[u.xx][w] = dp[a][cr] + u.yy;
                        q.push({dp[u.xx][w], u.xx, w});
                    }
                }
            }

            if(cr == 0)
            {
                for(auto u : g[a])
                {
                    if(okEdge(a, u.xx, u.yy))
                    {
                        for(int h = 1; h <= 2; h ++)
                        {
                            if(verif(a, u.xx, h))
                            if(dp[a][cr] < dp[u.xx][h])
                            {
                                dp[u.xx][h] = dp[a][cr];
                                q.push({dp[u.xx][h], u.xx, h});
                            }
                        }
                    }
                }
            }

            if(cr == 1 || cr == 2)
            {
                ///1-1 and 2-2
                for(auto u : g[a])
                {
                    if(okEdge(a, u.xx, u.yy) && verif(a, u.xx, cr))
                    {
                        if(dp[a][cr] < dp[u.xx][cr])
                        {
                            dp[u.xx][cr] = dp[a][cr];
                            q.push({dp[u.xx][cr], u.xx, cr});
                        }
                    }
                }
            }
        }
    }

    rez = min({dp[v][0], dp[v][1], dp[v][2], dp[v][3]});
}

void solve()
{
    distra(s, 0);
    distra(t, 1);

/*    distra(v, 2);

    lint mn = sqrInf;
    for(int i = 1; i <= n; i ++)
    {
        if(dist[i][0] + dist[i][1] == dist[t][0])
            mn = min(mn, dist[i][2]);
    }

    cout << mn << "\n";*/

    getDp();
}

void printFile()
{
    cout << rez << "\n";
}

int main()
{
    readFile();

    solve();

    printFile();

    return 0;
}

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