Submission #1210151

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210151		nvc2k8	Commuter Pass (JOI18_commuter_pass)	C++20	15 / 100	2096 ms	23068 KiB

commuter_pass

#include <bits/stdc++.h>
#define TASK "asdkjaskdj"
#define INT_LIM (int) 2147483647
#define LL_LIM (long long) 9223372036854775807
#define endl '\n'
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define BIT(i,x) (((i)>>(x))&1)
#define FOR(i,a,b) for(int i = (a); i<=(b); i++)
#define FORD(i,a,b) for(int i = (a); i>=(b); i--)
#define ll long long
#define pii pair<int,int>
using namespace std;
///------------------------------------------///
int n,m;
int s,t,x,y;
vector<pair<int,ll>> adj[100005];

void inp()
{
    cin >> n >> m;
    cin >> s >> t;
    cin >> x >> y;
    FOR(i, 1, m)
    {
        int u,v,c;
        cin >> u >> v >> c;
        adj[u].pb(mp(v,c));
        adj[v].pb(mp(u,c));
    }
}

ll distS[100005], distT[100005], distX[100005], distY[100005];

void dijkstra(int source, ll dist[100005])
{
    FOR(i, 1, n) dist[i] = LL_LIM;
    priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>> > q;
    q.push(mp(0,source)); dist[source] = 0;

    while (!q.empty())
    {
        int u = q.top().se; ll d = q.top().fi;
        q.pop();
        if (d>dist[u]) continue;
        for (auto V:adj[u])
        {
            int v = V.fi; ll w = V.se;
            if (d+w<dist[v])
            {
                dist[v] = d+w; q.push(mp(d+w, v));
            }
        }
    }
}

ll ans;
ll minx[100005], miny[100005];

void calc(int u)
{
    minx[u] = distX[u]; miny[u] = distY[u];

    for (auto V:adj[u])
    {
        int v = V.fi; ll w = V.se;

        if (distS[u]+w+distT[v]==distS[t])
        {
            calc(v);
            minx[u] = min(minx[u], minx[v]);
            miny[u] = min(miny[u], miny[v]);
        }
    }

    ans = min(ans, distX[u]+miny[u]);
    ans = min(ans, distY[u]+minx[u]);
}

void solve()
{
    dijkstra(s, distS);
    dijkstra(t, distT);
    dijkstra(x, distX);
    dijkstra(y, distY);
    ans = distX[y];
//    cout << ans << endl;

    calc(s);

    cout << ans << endl;
}

signed main()
{
    ///--------------------------///
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    if (fopen(TASK".INP","r")!=NULL)
    {
        freopen(TASK".INP","r",stdin);
        freopen(TASK".OUT","w",stdout);
    }
    ///--------------------------///

    int NTEST = 1;
    //cin >> NTEST;

    while (NTEST--)
    {
        inp();
        solve();
    }

    return 0;
}

///------------------------------------------///

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:102:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |         freopen(TASK".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
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(TASK".OUT","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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