Submission #1354103

#	Time	Username	Problem	Language	Result	Execution time	Memory
1354103		nguyenphuc2789	Commuter Pass (JOI18_commuter_pass)	C++17	31 / 100	221 ms	51032 KiB

commuter_pass

/*
    Author: nguyenphuc2789
    note: bestamiere, ge doc mi, avec tame
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define double long double
#define inl inline
const int LOG = 31;
const int maxn = 1e6 + 5;
const int MAX = 1e18;
const int MIN = -1e18;
const int MOD = 1e9 + 7;
int tc = 1;
int dist[maxn][3];
bool visited[maxn][3];
int n , m , s , t , x , y;
vector<pair<int , int>> adj[maxn];
struct Node
{
    int u , w;
    bool operator<(const Node &a) const
    {
        return w > a.w;
    }
};
struct Edge
{
    int u , v , w;
};
Edge g[maxn];
priority_queue<Node> pq[3];
void dijkstra(int idx)
{
    while (!pq[idx].empty())
    {
        int u = pq[idx].top().u;
        int distance = pq[idx].top().w;
        pq[idx].pop();
        if (distance > dist[u][idx])
        {
            continue;
        }
        if (visited[u][idx])
        {
            continue;
        }
        visited[u][idx] = true;
        for (auto &i : adj[u])
        {
            int v = i.first;
            int w = i.second;
            if (dist[v][idx] > dist[u][idx] + w)
            {
                dist[v][idx] = dist[u][idx] + w;
                pq[idx].push({v , dist[v][idx]});
            }
        }
    }
}
void solve()
{
    cin >> n >> m >> s >> t >> x >> y;
    for (int i = 1 ; i <= m ; ++i)
    {
        int u , v , w;
        cin >> u >> v >> w;
        g[i] = {u , v , w};
        adj[u].push_back({v , w});
        adj[v].push_back({u , w});
    }
    for (int i = 1 ; i <= n ; ++i)
    {
        dist[i][0] = dist[i][1] = dist[i][2] = MAX;
        visited[i][0] = visited[i][1] = visited[i][2] = false;
    }
    dist[s][0] = 0;
    pq[0].push({s , dist[s][0]});
    dijkstra(0);
    dist[t][1] = 0;
    pq[1].push({t , dist[t][1]});
    dijkstra(1);
    for (int i = 1 ; i <= m ; ++i)
    {
        int u = g[i].u;
        int v = g[i].v;
        int w = g[i].w;
        if (dist[u][0] + w + dist[v][1] == dist[t][0] || dist[u][1] + w + dist[v][0] == dist[t][0])
        {
            adj[u].push_back({v , 0});
            adj[v].push_back({u , 0});
        }
    }
    dist[x][2] = 0;
    pq[2].push({x , dist[x][2]});
    dijkstra(2);
    cout << (dist[y][2] == MAX ? 0ll : dist[y][2]) << '\n';
}
void input()
{
    // cin >> tc;
}
void process()
{
    while (tc--)
    {
        solve();
    }
}
void setup()
{
#ifndef ONLINE_JUDGE
    freopen("test.inp", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}
signed main()
{
    // setup();
    input();
    process();
    return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void setup()':
commuter_pass.cpp:114:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |     freopen("test.inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:115:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  115 |     freopen("test.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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