제출 #233742

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
233742		Coroian_David	Commuter Pass (JOI18_commuter_pass)	C++11	0 / 100	625 ms	20376 KiB

commuter_pass

#include <bits/stdc++.h>

#define MAX_N 100000

#define xx first
#define yy second

using namespace std;

typedef long long lint;

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][2];
lint dist[MAX_N + 1][2];
lint dp[MAX_N + 1][4];
int vi[MAX_N + 1][4];

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

struct elem
{
    int d, 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(b == s || b == t)
        return 0;

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

    getDp();
}

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

int main()
{
    readFile();

    solve();

    printFile();

    return 0;
}

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

commuter_pass.cpp: In function 'void getDp()':
commuter_pass.cpp:140:43: warning: narrowing conversion of 'dp[u.std::pair<int, int>::first][w]' from 'lint {aka long long int}' to 'int' inside { } [-Wnarrowing]
                         q.push({dp[u.xx][w], u.xx, w});
                                 ~~~~~~~~~~^
commuter_pass.cpp:157:51: warning: narrowing conversion of 'dp[u.std::pair<int, int>::first][h]' from 'lint {aka long long int}' to 'int' inside { } [-Wnarrowing]
                                 q.push({dp[u.xx][h], u.xx, h});
                                         ~~~~~~~~~~^
commuter_pass.cpp:174:48: warning: narrowing conversion of 'dp[u.std::pair<int, int>::first][cr]' from 'lint {aka long long int}' to 'int' inside { } [-Wnarrowing]
                             q.push({dp[u.xx][cr], u.xx, cr});
                                     ~~~~~~~~~~~^

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