Submission #915042

#	Time	Username	Problem	Language	Result	Execution time	Memory
915042		asdfGuest	Commuter Pass (JOI18_commuter_pass)	C++14	31 / 100	494 ms	45132 KiB

commuter_pass

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

#define INF (1000000000ll * 200000ll)

typedef long long ll;

struct adj_t {
    int nx;
    ll w;
};

int n, m;
vector<adj_t> adj[100001], adj_inv[100001];

vector<ll> dijkstra(int start, vector<adj_t> *adj_mat) {
    vector<ll> dist(n + 1, INF);
    priority_queue<pair<ll, int>> heap;
    
    heap.push({-0ll, start});
    dist[start] = 0ll;

    while (!heap.empty()) {
        int nw = heap.top().second;
        ll d = -heap.top().first;
        heap.pop();
        
        if (d > dist[nw])
            continue;
        
        for (int i = 0; i < adj_mat[nw].size(); i++) {
            auto nex = adj_mat[nw][i];
            ll new_cost = d + nex.w;

            if (new_cost < dist[nex.nx]) {
                heap.push({-new_cost, nex.nx});
                dist[nex.nx] = new_cost;
            }
        }
    }

    return dist;
}
vector<pair<int, int>> shortest_path(int start, int end, vector<adj_t> *adj_mat) {
    vector<ll> dist(n + 1, INF);
    vector<int> memo[100001];
    vector<pair<int, int>> edge;

    priority_queue<pair<ll, int>> heap;
    
    heap.push({-0, start});
    dist[start] = 0;

    while (!heap.empty()) {
        int nw = heap.top().second;
        ll d = -heap.top().first;
        heap.pop();

        if (d > dist[nw])
            continue;
        
        for (int i = 0; i < adj_mat[nw].size(); i++) {
            auto nex = adj_mat[nw][i];
            ll new_cost = d + nex.w;

            if (new_cost < dist[nex.nx]) {
                heap.push({-new_cost, nex.nx});
                dist[nex.nx] = new_cost;

                memo[nex.nx].clear();
                memo[nex.nx].push_back(nw);
            }
            else if (new_cost == dist[nex.nx])
                memo[nex.nx].push_back(nw);
        }
    }

    bool visit[100001] = {false};
    queue<int> bfsQ;

    bfsQ.push(end);
    visit[end] = true;

    while (!bfsQ.empty()) {
        int nw = bfsQ.front();
        bfsQ.pop();

        for (int i = 0; i < memo[nw].size(); i++) {
            int nex = memo[nw][i];

            if (!visit[nex]) {
                bfsQ.push(nex);
                visit[nex] = true;
            }

            edge.push_back({nex, nw});
        }
    }

    return edge;
}

int main(void) {
    int s, t, u, v;
    scanf("%d %d %d %d %d %d", &n, &m, &s, &t, &u, &v);

    for (int i = 0; i < m; i++) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        adj[a].push_back({b, (ll)c});
        adj[b].push_back({a, (ll)c});
        adj_inv[a].push_back({b, (ll)c});
        adj_inv[b].push_back({a, (ll)c});
    }

    auto edge = shortest_path(s, t, adj);
    for (int i = 0; i < edge.size(); i++) {
        adj[edge[i].first].push_back({edge[i].second, 0ll});
        adj_inv[edge[i].second].push_back({edge[i].first, 0ll});
    }
    
    auto udis1 = dijkstra(u, adj), vdis1 = dijkstra(v, adj_inv);
    auto udis2 = dijkstra(u, adj_inv), vdis2 = dijkstra(v, adj);
    ll ans = INF;
    
    for (int i = 1; i <= n; i++)
        ans = min(ans, min(udis1[i] + vdis1[i], udis2[i] + vdis2[i]));

    printf("%lld\n", ans);
  
    return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'std::vector<long long int> dijkstra(int, std::vector<adj_t>*)':
commuter_pass.cpp:35:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<adj_t>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |         for (int i = 0; i < adj_mat[nw].size(); i++) {
      |                         ~~^~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp: In function 'std::vector<std::pair<int, int> > shortest_path(int, int, std::vector<adj_t>*)':
commuter_pass.cpp:66:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<adj_t>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |         for (int i = 0; i < adj_mat[nw].size(); i++) {
      |                         ~~^~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:92:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |         for (int i = 0; i < memo[nw].size(); i++) {
      |                         ~~^~~~~~~~~~~~~~~~~
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:121:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |     for (int i = 0; i < edge.size(); i++) {
      |                     ~~^~~~~~~~~~~~~
commuter_pass.cpp:109:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |     scanf("%d %d %d %d %d %d", &n, &m, &s, &t, &u, &v);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:113:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |         scanf("%d %d %d", &a, &b, &c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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