Submission #385433

#	Time	Username	Problem	Language	Result	Execution time	Memory
385433		ngpin04	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	405 ms	24864 KiB

commuter_pass

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
using namespace std;
const int N = 1e5 + 5;
const long long oo = 1e18;
 
vector <pair <int, int>> adj[N];
 
long long f[N];
long long g[N];
long long dis[2][N];
long long dp[2][N];
long long invdp[2][N];
 
vector <int> order;
 
int n,m,s,t,u,v;

bool vis[N];

template <typename T>
bool mini(T &a, T b)
{
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
 
void dijkstra(int s, long long dis[])
{
    for (int i = 1; i <= n; i++)
        dis[i] = oo;
 
    dis[s] = 0;
    priority_queue <pair <long long, int>> heap;
    heap.push(mp(0, s));
    while (heap.size()) {
        int u = heap.top().se;
        long long cur = -heap.top().fi;
        heap.pop();
        if (dis[u] != cur)
            continue;
        for (pair <int, int> e : adj[u])
            if (mini(dis[e.fi], cur + e.se))
                heap.push(mp(-dis[e.fi], e.fi));
    }
}
 
void dfs(int u)
{
  	vis[u] = true;
    for (pair <int, int> e : adj[u]) {
        int v = e.fi;
        int w = e.se;
        if (!vis[v] && f[u] + g[v] + w == f[t])
            dfs(v);
    }
    order.push_back(u);
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("file.inp","r",stdin);
    cin >> n >> m;
    cin >> s >> t >> u >> v;
    for (int i = 1; i <= m; i++) {
        int u,v,w;
        cin >> u >> v >> w;
        adj[u].push_back(mp(v, w));
        adj[v].push_back(mp(u, w));
    }
    dijkstra(s, f);
    dijkstra(t, g);
    dijkstra(u, dis[0]);
    dijkstra(v, dis[1]);
    dfs(s);
    reverse(order.begin(), order.end());
    for (int j = 0; j <= 1; j++)
    for (int i = 1; i <= n; i++)
        dp[j][i] = oo;
    for (int i : order) {
        for (int j = 0; j <= 1; j++) {
            dp[j][i] = dis[j][i];
            for (pair <int, int> e : adj[i]) {
                int pre = e.fi;
                int w = e.se;
                if (f[pre] + g[i] + w == f[t])
                    dp[j][i] = min(dp[j][i], dp[j][pre]);
            }
        }
    }
    reverse(order.begin(), order.end());
    for (int i : order) {
        for (int j = 0; j <= 1; j++) {
            invdp[j][i] = dis[j][i];
            for (pair <int, int> e : adj[i]) {
                int pre = e.fi;
                int w = e.se;
                if (f[i] + g[pre] + w == f[t])
                    invdp[j][i] = min(invdp[j][i], invdp[j][pre]);
            }
        }
    }
 
    long long ans = dis[0][v];
    for (int i = 1; i <= n; i++)
    for (int j = 0; j <= 1; j++)
        ans = min(ans, dp[j][i] + invdp[j ^ 1][i]);
    cout << ans;
    return 0;
}

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