제출 #869382

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
869382		vjudge1	Commuter Pass (JOI18_commuter_pass)	C++14	0 / 100	254 ms	23636 KiB

commuter_pass

#include <iostream>
#include <limits>
#include <vector>
#include <set>
#include <cstdint>

using namespace std;
using Pair = pair<int64_t, int64_t>;

struct Edge
{
    int64_t w, v, u;
};

constexpr int64_t maxn = 100000, maxm = 200000, inf = numeric_limits<int64_t>::max();
int64_t n, m, x1, y1, x2, y2;
Edge edge[maxm + 1];
vector<int64_t> adj[maxn + 1];
bool isVisited[maxn + 1];

bool DFS(int64_t v = x1)
{
    isVisited[v] = true;

    bool result = v == y1;
    for (int64_t e : adj[v])
    {
        int64_t u = edge[e].v + edge[e].u - v;
        if (isVisited[u])
            continue;

        if (DFS(u))
        {
            edge[e].w = 0;
            result = true;
        }
    }

    return result;
}

int64_t Dijkstra()
{
    for (int64_t i = 1; i <= n; i++)
        isVisited[i] = false;
    set<Pair> q;
    auto d = vector<int64_t>(n + 1, inf);

    q.insert(make_pair(0, x2));
    d[x2] = 0;

    while (q.size() > 0)
    {
        int64_t v = q.begin()->second;
        q.erase(q.begin());
        isVisited[v] = true;

        for (int64_t e : adj[v])
        {
            int64_t u = edge[e].v + edge[e].u - v;
            if (isVisited[u])
                continue;

            if (d[u] > d[v] + edge[e].w)
            {
                d[u] = d[v] + edge[e].w;
                q.insert(make_pair(d[u], u));
            }
        }
    }

    return d[y2];
}

int main()
{
    cin >> n >> m >> x1 >> y1 >> x2 >> y2;
    for (int64_t i = 1; i <= m; i++)
    {
        cin >> edge[i].v >> edge[i].u >> edge[i].w;
        adj[edge[i].v].push_back(i);
        adj[edge[i].u].push_back(i);
    }

    for (int64_t i = 1; i <= n; i++)
        isVisited[i] = false;
    DFS();
    cout << Dijkstra() << '\n';

    return 0;
}

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