Submission #833608

#	Time	Username	Problem	Language	Result	Execution time	Memory
833608		vjudge1	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	270 ms	26000 KiB

commuter_pass

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define eb emplace_back
#define task ""
#define fast ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define nx freopen (task".inp","r",stdin), freopen (task".out","w",stdout);
#define fi first
#define se second
#define pii pair <ll, ll>
#define tii tuple <int, int, int>
using namespace std;
const int nmax = 1e5 + 2;
int n, m;
int src[4];
ll d[4][nmax], dpuv[nmax], dpvu[nmax], ans = 1e18;
vector <pii> adj[nmax];
vector <int> cay[nmax];
void cal(int ith)
{
    memset(d[ith], 0x3f, sizeof d[ith]);
    d[ith][src[ith]] = 0;
    priority_queue <pii, vector <pii>, greater<pii> > q;
    q.emplace(0, src[ith]);
    while(q.size())
    {
        auto [dist, u] = q.top();
        q.pop();
        if (dist > d[ith][u]) continue;
        for (auto &[v, w] : adj[u])
        {
            if (d[ith][v] > d[ith][u] + w)
                q.emplace(d[ith][v] = d[ith][u] + w, v);
        }
    }
}
bool vs[nmax];
void dfsuv(int u)
{
    if (vs[u]) return;
    vs[u] = 1;
    for (auto &v : cay[u])
    {
        dfsuv(v);
        dpuv[u] = min({dpuv[u], dpuv[v], d[2][v]});
    }
    if (dpuv[u] < 1e18)
        ans = min(ans, dpuv[u] + d[3][u]);
}
void dfsvu(int u)
{
    if (vs[u]) return;
    vs[u] = 1;
    for (auto &v : cay[u])
    {
        dfsvu(v);
        dpvu[u] = min({dpvu[u], dpvu[v], d[3][v]});
    }
    if (dpvu[u] < 1e18)
        ans = min(ans, dpvu[u] + d[2][u]);
}
int main ()
{
    if (ifstream(task".inp")) nx
    fast
    cin >> n >> m;
    for (int i = 0; i < 4; ++i)
        cin >> src[i]; // s0 t1 u2 v3
    for (int u, v, w, i = 1; i <= m; ++i)
    {
        cin >> u >> v >> w;
        adj[u].eb(v, w);
        adj[v].eb(u, w);
    }
    for (int i = 0; i < 4; ++i)
        cal(i);
    memset(dpuv, 0x3f, sizeof dpuv);
    memset(dpvu, 0x3f, sizeof dpvu);
    for (int u = 1; u <= n; ++u)
    {
        for (auto &[v, w] : adj[u])
        {
            if (d[0][u] + w + d[1][v] == d[0][src[1]])
                cay[u].eb(v);
        }
    }
    dfsuv(src[0]);
    memset(vs, 0, sizeof vs);
    dfsvu(src[0]);
    cout << min(ans, d[2][src[3]]);
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:7:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 | #define nx freopen (task".inp","r",stdin), freopen (task".out","w",stdout);
      |            ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:64:31: note: in expansion of macro 'nx'
   64 |     if (ifstream(task".inp")) nx
      |                               ^~
commuter_pass.cpp:7:52: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 | #define nx freopen (task".inp","r",stdin), freopen (task".out","w",stdout);
      |                                            ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:64:31: note: in expansion of macro 'nx'
   64 |     if (ifstream(task".inp")) nx
      |                               ^~

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