Submission #1123411

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123411		whoknow	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	462 ms	21548 KiB

commuter_pass

#include <bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define MAXN 100005
#define ii pair<ll,int>
#define bit(i,j) ((i>>j)&1)
#define sz(i) (int)i.size()
#define endl '\n'
using namespace std;
const ll INF  = 1e18 + 7;
int n, m, S, T, U, V;
vector<ii>g[MAXN];
namespace sub1
{
ll d[4][MAXN], dp1[MAXN], dp2[MAXN];
void bfs(int k, int st)
{
    for(int i = 1; i <= n; i++)
        d[k][i] = INF;
    priority_queue<ii, vector<ii>, greater<ii>>q;
    q.push({0, st});
    d[k][st] = 0;
    while(q.empty() != 1)
    {
        ii top = q.top();
        q.pop();
        ll kc = top.F;
        int u = top.S;
        for(ii i : g[u])
        {
            int v = i.F, w = i.S;
            if(d[k][v] > kc + w)
            {
                d[k][v] = kc + w;
                q.push({d[k][v], v});
            }
        }
    }
}
void calc1()
{
    priority_queue<ii, vector<ii>, greater<ii>>q;
    for(int i = 1; i <= n; i++)
    {
        dp1[i] = d[2][i];
        q.push({dp1[i], i});
    }
    while(q.empty() != 1)
    {
        ii top = q.top();
        q.pop();
        ll kc = top.F;
        int u = top.S;
        for(ii i : g[u])
        {
            int v = i.F, w = i.S;
            if(d[0][v] + d[1][v] == d[0][T] && d[0][v] == d[0][u] + w && dp1[v] > kc)
            {
                dp1[v] = kc;
                q.push({kc, v});
            }
        }
    }
}
void calc2()
{
    priority_queue<ii, vector<ii>, greater<ii>>q;
    for(int i = 1; i <= n; i++)
    {
        dp2[i] = d[2][i];
        q.push({dp2[i], i});
    }
    while(q.empty() != 1)
    {
        ii top = q.top();
        q.pop();
        ll kc = top.F;
        int u = top.S;
        for(ii i : g[u])
        {
            int v = i.F, w = i.S;
            if(d[0][v] + d[1][v] == d[0][T] && d[1][v] == d[1][u] + w && dp2[v] > kc)
            {
                dp2[v] = kc;
                q.push({kc, v});
            }
        }
    }
}
void solve()
{
    bfs(0, S);
    bfs(1, T);
    bfs(2, U);
    bfs(3, V);
    calc1();
    calc2();
    ll res = d[2][V];
    for(int i = 1; i <= n; i++)
        res = min(res, d[3][i] + min(dp1[i], dp2[i]));
    cout << res;
}
}
main()
{
    if(fopen("TEST.inp", "r"))
    {
        freopen("TEST.inp", "r", stdin);
        freopen("TEST.out", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> S >> T >> U >> V;
    for(int i = 1; i <= m; i++)
    {
        int x, y, z;
        cin >> x >> y >> z;
        g[x].push_back({y, z});
        g[y].push_back({x, z});
    }
    sub1::solve();
//    cerr << "\nTIME: " << 1.0 * clock() / CLOCKS_PER_SEC << endl;
}

Compilation message (stderr)

commuter_pass.cpp:105:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  105 | main()
      | ^~~~
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:109:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |         freopen("TEST.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:110:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |         freopen("TEST.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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