Submission #1066795

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066795		vjudge1	Commuter Pass (JOI18_commuter_pass)	C++17	16 / 100	230 ms	45156 KiB

commuter_pass

#include<iostream>
#include<algorithm>
#include<utility>
#include<vector>
#include<queue>
using namespace std;
using lli = long long;
const lli maxN = 2e5 + 5;
struct Tedge
{
    lli x,y,w;
}
e[maxN];
lli n,m,a,b,c,d;
vector<lli> adj[maxN],adj1[maxN],adj2[maxN];
priority_queue<pair<lli,lli>> q;
lli da[maxN],db[maxN],dc[maxN],dd[maxN],di[maxN],res;
lli dp[maxN],deg[maxN];
void input()
{
    res = 1e18;
    cin >> n >> m >> a >> b >> c >> d;
    for (lli i = 1;i <= m;++i)
    {
        cin >> e[i].x >> e[i].y >> e[i].w;
        adj[e[i].x].push_back(i);
        adj[e[i].y].push_back(i);
    }
}
void dijkstra(lli a)
{
    fill(di + 1,di + n + 1,1e18);
    di[a] = 0;
    while (!q.empty()) q.pop();
    q.push({-di[a],a});
    while (!q.empty())
    {
        lli u = q.top().second,p = q.top().first;
        q.pop();
        if (p != -di[u]) continue;
        for (lli i : adj[u])
        {
            lli v = e[i].x + e[i].y - u;
            if (di[v] > di[u] + e[i].w)
            {
                di[v] = di[u] + e[i].w;
                q.push({-di[v],v});
            }
        }
    }
}
void calc(lli u)
{
    dp[u] = min(dp[u],dc[u]);
    res = min(dp[u] + dd[u],res);
    for (lli i : adj1[u])
    {
        lli v = e[i].x + e[i].y - u;
        dp[v] = min(dp[v],dp[u]);
        res = min(dp[v] + dd[v],res);
        --deg[v];
        if (deg[v] == 0) calc(v);
    }
}
void solve()
{
    dijkstra(a);swap(di,da);
    dijkstra(b);swap(di,db);
    dijkstra(c);swap(di,dc);
    dijkstra(d);swap(di,dd);
    fill(deg + 1,deg + n + 1,0);
    for (lli i = 1;i <= m;++i)
    {
        if (da[e[i].x] + db[e[i].y] + e[i].w == da[b]) {adj1[e[i].x].push_back(i);deg[e[i].y]++;}
        if (da[e[i].y] + db[e[i].x] + e[i].w == da[b]) {adj1[e[i].y].push_back(i);deg[e[i].x]++;}
    }
    res = dc[d];
    fill(dp + 1,dp + n + 1,1e18);calc(a);swap(dd,dc);swap(d,c);
    fill(dp + 1,dp + n + 1,1e18);calc(a);
    cout << res;
}
//a = 1, x = 3, y = 2, b = 4
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
//    freopen("C.inp","r",stdin);
//    freopen("C.out","w",stdout);
    input();
    solve();
}

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