Submission #204068

#	Time	Username	Problem	Language	Result	Execution time	Memory
204068		Kastanda	Commuter Pass (JOI18_commuter_pass)	C++11	0 / 100	380 ms	27116 KiB

commuter_pass

// In The Name Of The Queen
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
const int N = 100005;
int n, m, st, fn, vs, ut, M[N], M2[N];
ll Mn = LLONG_MAX, dp[N];
vector < int > Ad[N], Adt[N];
vector < pair < int , int > > Adj[N];
priority_queue < pair < ll , int > > Pq;
vector < ll > Dst, Dvs, Dut;
vector < ll > SSSP(int v)
{
    vector < ll > D(n + 1, (ll)(1e18));
    D[v] = 0; Pq.push({0, v});
    while (Pq.size())
    {
        ll d = - Pq.top().first;
        v = Pq.top().second; Pq.pop();
        if (d > D[v])
            continue;
        for (auto u : Adj[v])
            if (D[u.x] > D[v] + u.y)
                D[u.x] = D[v] + u.y, Pq.push({-D[u.x], u.x});
    }
    return (D);
}
void DFS(int v)
{
    M[v] = 1;
    dp[v] = Dut[v];
    for (int u : Ad[v])
    {
        if (!M2[u])
            continue;
        if (!M[u])
            DFS(u);
        dp[v] = min(dp[v], dp[u]);
        Mn = min(Mn, Dvs[v] + dp[u]);
    }
}
void DFS2(int v)
{
    M2[v] = 1;
    for (int u : Adt[v])
        if (!M2[u])
            DFS2(u);
}
int main()
{
    scanf("%d%d%d%d%d%d", &n, &m, &st, &fn, &vs, &ut);
    for (int i = 1; i <= m; i ++)
    {
        int v, u, w;
        scanf("%d%d%d", &v, &u, &w);
        Adj[v].push_back({u, w});
        Adj[u].push_back({v, w});
    }
    Dst = SSSP(st);
    Dvs = SSSP(vs);
    Dut = SSSP(ut);
    for (int i = 1; i <= n; i ++)
        for (auto u : Adj[i])
            if (Dst[u.x] == Dst[i] + u.y)
                Ad[i].push_back(u.x),
                Adt[u.x].push_back(i);
    Mn = Dvs[ut];
    DFS2(fn);
    DFS(1);
    Dvs.swap(Dut);
    memset(M, 0, sizeof(M));
    DFS(1);
    return !printf("%lld\n", Mn);
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:53:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d%d%d%d", &n, &m, &st, &fn, &vs, &ut);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:57:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &v, &u, &w);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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