Submission #1086443

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086443		themaver1cks	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	308 ms	47876 KiB

commuter_pass

/**
｡∠(*・ω･)っ  ⌒ 由 ~    ((　,,・з・,,　))
 _Π_____。
/______/~＼
｜ 田田｜門｜
why im so dumb man >.<
**/
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
#define sz(x) (int)(x).size()
#define el "\n"

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,int> pli;
//
struct EDGE
{
    int u, v, w;
};
// var dec
const int maxn = 1e5 + 3;
const ll inf = 1e18;
int n, m;
int s, t, u, v;
// ds dec
vector <EDGE> edges;
vector <ll> distS(maxn, inf), distT(maxn, inf), distU(4*maxn, inf);
vector <pii> g[4*maxn];
//
void dijkstra(int s, vector<ll>& d)
{
    priority_queue<pli, vector<pli>, greater<pli>> pq;
    pq.push({0, s});
    d[s] = 0;
    while (sz(pq))
    {
        ll e = pq.top().fi;
        int u = pq.top().se;
        pq.pop();
        if (e != d[u]) continue;
        for (auto x: g[u])
        {
            int v = x.fi, w = x.se;
            if (d[v] > d[u] + w)
            {
                d[v] = d[u] + w;
                pq.push({d[v], v});
            }
        }
    }
}
//
void solve()
{
    cin >> n >> m >> s >> t >> u >> v;
    for (int i=1; i<=m; ++i)
    {
        int u, v, w; cin >> u >> v >> w;
        edges.pb({u, v, w});
        g[u].pb({v, w});
        g[v].pb({u, w});
    }
    dijkstra(s, distS);
    dijkstra(t, distT);
    for (auto e: edges)
    {
        int u = e.u, v = e.v, w = e.w;
        g[3*n+u].pb({3*n+v, w});
        g[3*n+v].pb({3*n+u, w});
        if ((distS[u] + distT[v] + w) == distS[t])
        {
            g[n+u].pb({n+v, 0});
            g[2*n+v].pb({2*n+u, 0});
        }
        if ((distS[v] + distT[u] + w) == distS[t])
        {
            g[n+v].pb({n+u, 0});
            g[2*n+u].pb({2*n+v, 0});
        }
    }
    for (int i=1; i<=n; ++i)
    {
        g[i].pb({n+i, 0});
        g[i].pb({2*n+i, 0});
        g[n+i].pb({3*n+i, 0});
        g[2*n+i].pb({3*n+i, 0});
    }
    dijkstra(u, distU);
    cout << distU[3*n+v] << el;
}
//
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    if (fopen("lmao.inp", "r"))
    {
        freopen("lmao.inp", "r", stdin);
        freopen("lmao.out", "w", stdout);
    }
    int t = 1;
//    cin >> t;
    while (t--) solve();
    return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int32_t main()':
commuter_pass.cpp:103:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |         freopen("lmao.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:104:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |         freopen("lmao.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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