Submission #1013431

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013431		daffuwu	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	265 ms	35600 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

long long n, m, dst[100069][4], src[4], a, b, c, ans, dp[100069][2];
vector<pair<long long, long long> > al[100069];
vector<long long> al1[100069], par[100069];

void dij(long long src, long long idx)
{
    long long i;
    priority_queue<pair<long long, long long> > pq;
    for (i=1; i<=n; i++) dst[i][idx] = 1e15;
    dst[src][idx] = 0;
    pq.push({0, src});
    for (; !pq.empty(); )
    {
        auto [w, u] = pq.top();
        pq.pop();
        w = -w;
        if (dst[u][idx]<w) continue;
        for (auto [v, w]:al[u])
        {
            if (dst[v][idx]>dst[u][idx]+w)
            {
                dst[v][idx] = dst[u][idx]+w;
                par[v].clear();
                pq.push({-dst[v][idx], v});
            }
            if (dst[v][idx] == dst[u][idx]+w) par[v].push_back(u);
        }
    }
    if (idx == 0)
    {
        for (i=1; i<=n; i++)
        {
            for (auto u:par[i]) al1[u].push_back(i);
        }
    }
    for (i=1; i<=n; i++) par[i].clear();
}

long long slv(long long u, long long idx)
{
    if (dp[u][idx] != -1) return dp[u][idx];
    if (u == src[1]) return dp[u][idx] = dst[u][idx+2];
    dp[u][idx] = 1e15;
    for (auto v:al1[u]) dp[u][idx] = min(dp[u][idx], slv(v, idx));
    if (dp[u][idx] != 1e15) dp[u][idx] = min(dp[u][idx], dst[u][idx+2]);
    return dp[u][idx];
}

int main() 
{
    long long i, j, ii;
    scanf("%lld%lld%lld%lld%lld%lld", &n, &m, src, src+1, src+2, src+3);
    for (i=1; i<=m; i++)
    {
        scanf("%lld%lld%lld", &a, &b, &c);
        al[a].push_back({b, c});
        al[b].push_back({a, c});
    }
    for (i=0; i<=3; i++) dij(src[i], i);
    memset(dp, -1, sizeof(dp));
    ans = dst[src[3]][2];
    for (i=1; i<=n; i++)
    {
        for (j=0; j<=1; j++)
        {
            ans = min(ans, dst[i][j+2]+slv(i, 1-j));
        }
    }
    printf("%lld\n", ans);
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void dij(long long int, long long int)':
commuter_pass.cpp:20:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   20 |         auto [w, u] = pq.top();
      |              ^
commuter_pass.cpp:24:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   24 |         for (auto [v, w]:al[u])
      |                   ^
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:57:21: warning: unused variable 'ii' [-Wunused-variable]
   57 |     long long i, j, ii;
      |                     ^~
commuter_pass.cpp:58:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |     scanf("%lld%lld%lld%lld%lld%lld", &n, &m, src, src+1, src+2, src+3);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:61:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |         scanf("%lld%lld%lld", &a, &b, &c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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