Submission #854718

#	Time	Username	Problem	Language	Result	Execution time	Memory
854718		hungnt	Commuter Pass (JOI18_commuter_pass)	C++14	0 / 100	66 ms	15956 KiB

commuter_pass

#include <bits/stdc++.h>
#define pii pair<long long, int>
#define fi first
#define se second
using namespace std;

const long long inf = 1e18;

int n, m;
int s[4];
vector<pair<int, int>> adj[100005];
vector<int> tree[100005];
long long d[4][100005], dp[100005][2], ans;
bool vi[100005];
priority_queue<pii, vector<pii>, greater<pii>> pq;

void dijkstra(int x)
{
    d[x][s[x]] = 0;
    pq.push({0, s[x]});
    while(!pq.empty())
    {
        int u = pq.top().se;
        long long w = pq.top().fi;
        pq.pop();
        if(d[x][u] != w) continue;
        for(auto y : adj[u])
        {
            int v = y.fi, cost = y.se;
            if(d[x][v] > d[x][u] + cost)
                pq.push({d[x][v] = d[x][u] + cost, v});
        }
    }
}

void dfs(int u)
{
    if (vi[u]) return;
    vi[u] = 1;
    for(int v : tree[u])
    {
        dfs(v);
        dp[u][0] = min(dp[u][0], min(dp[v][0], d[2][v]));
        dp[u][1] = min(dp[u][1], min(dp[v][1], d[3][v]));
    }
    if (dp[u][0] < inf)  ans = min(ans, dp[u][0] + d[3][u]);
    if (dp[u][1] < inf)  ans = min(ans, dp[u][1] + d[2][u]);
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for(int i = 0; i <= 3; i++) cin >> s[i];
    int u, v, w;
    while(m--)
    {
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    memset(d, 0xef, sizeof d);
    for(int i = 0; i <= 3; i++) dijkstra(i);
    for(int i = 1; i <= n; i++)
        for(auto x : adj[i])
        {
            if(d[0][i] + x.se + d[1][x.fi] != d[0][s[1]]) continue;
            tree[i].push_back(x.fi);
        }
    ans = d[2][s[3]];
    memset(dp, 0x3f, sizeof(dp));
    dfs(s[0]);
    cout << ans;
	return 0;
}

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