Submission #92357

#	Time	Username	Problem	Language	Result	Execution time	Memory
92357		Alexa2001	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	446 ms	19604 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll,int> Pair;
const int Nmax = 1e5 + 5;

vector<ll> distS, distT, distU, distV;
int N, M, S, T, U, V;
vector< pair<int,int> > v[Nmax];
ll dp[Nmax];
vector<int> nodes;

void dijkstra(int node, vector<ll> &dist)
{
    dist.resize(N+1);
    int i;
    for(i=1; i<=N; ++i) dist[i] = 1e18; dist[node] = 0;

    priority_queue< Pair, vector<Pair>, greater<Pair> > heap;
    heap.push({0, node});

    while(heap.size())
    {
        int node; ll D;
        node = heap.top().second;
        D = heap.top().first;
        heap.pop();

        if(dist[node] != D) continue;

        for(auto it : v[node])
            if(dist[it.first] > D + it.second)
            {
                dist[it.first] = D + it.second;
                heap.push({ dist[it.first], it.first });
            }
    }
}

bool cmp(int x, int y)
{
    return distS[x] < distS[y];
}

ll solve(int a, int b, int c, int d, vector<ll> &A, vector<ll> &B, vector<ll> &C, vector<ll> &D)
{
    int i;
    for(i=1; i<=N; ++i) dp[i] = 1e18;
    dp[a] = C[a];

    for(auto node : nodes)
    {
        for(auto it : v[node])
            if(A[node] == A[it.first] + it.second)
                dp[node] = min(dp[node], dp[it.first]);
        dp[node] = min(dp[node], C[node]);
    }

    ll ans = 1e18;
    for(auto node : nodes)
        if(A[node] + B[node] == A[b])
            ans = min(ans, dp[node] + D[node]);
    return ans;
}

int main()
{
 //   freopen("input", "r", stdin);
    cin.sync_with_stdio(false);

    cin >> N >> M >> S >> T >> U >> V;

    int i, x, y, cost;
    for(i=1; i<=M; ++i)
    {
        cin >> x >> y >> cost;
        v[x].push_back({y, cost});
        v[y].push_back({x, cost});
    }

    dijkstra(S, distS);
    dijkstra(T, distT);
    dijkstra(U, distU);
    dijkstra(V, distV);

    for(i=1; i<=N; ++i) nodes.push_back(i);
    sort(nodes.begin(), nodes.end(), cmp);

    ll ans = distU[V];
    ans = min(ans, solve(S, T, U, V, distS, distT, distU, distV));
    ans = min(ans, solve(S, T, V, U, distS, distT, distV, distU));
    cout << ans << '\n';

    return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void dijkstra(int, std::vector<long long int>&)':
commuter_pass.cpp:19:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for(i=1; i<=N; ++i) dist[i] = 1e18; dist[node] = 0;
     ^~~
commuter_pass.cpp:19:41: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
     for(i=1; i<=N; ++i) dist[i] = 1e18; dist[node] = 0;
                                         ^~~~

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