Submission #1066154

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066154		vjudge1	Commuter Pass (JOI18_commuter_pass)	C++17	15 / 100	2063 ms	45644 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];
struct Tadj
{
    lli v,w;
};
lli n,m,a,b,c,d;
vector<lli> adj1[maxN],adj2[maxN];
vector<Tadj> adj[maxN];
lli da[maxN],db[maxN],dc[maxN],dd[maxN],di[maxN],res;
lli dp[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({e[i].y,e[i].w});
        adj[e[i].y].push_back({e[i].x,e[i].w});
    }
}
struct Titem
{
    lli v,dlab = 1e18;
    bool operator < (const Titem& other) const
    {
        return other.dlab < dlab;
    }
    bool valid() const
    {
        return dlab == di[v];
    }
};
bool relax(lli u,lli v,lli w)
{
    if (di[v] > di[u] + w)
    {
        di[v] = di[u] + w;
        return true;
    }
    return false;
}
priority_queue<Titem> q;
void dijkstra(lli a)
{
    while (!q.empty()) q.pop();
    fill(di + 1,di + n + 1,1e18);
    di[a] = 0;
    q.push({a,0});
    while (!q.empty())
    {
        Titem p = q.top();q.pop();
        if (!p.valid()) continue;
        //if (a == 6) cout << adj[6].back().v << "a\n";
        lli u = p.v;
        for (Tadj a : adj[u])
            if (relax(u,a.v,a.w)) q.push({a.v,di[a.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]);
        calc(v);
    }
}
void solve()
{
    dijkstra(a);swap(di,da);
    dijkstra(b);swap(di,db);
    dijkstra(c);swap(di,dc);
    dijkstra(d);swap(di,dd);
    //cout << da[1] << " " << db[1] << "\n";
    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);
            //cout << e[i].x << " " << e[i].y << '\n';
        }
        if (da[e[i].y] + db[e[i].x] + e[i].w == da[b])
        {
            adj1[e[i].y].push_back(i);
            //cout << e[i].x << " " << e[i].y << '\n';
        }
    }
    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: 0 / 16
• Subtask 2: 15 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 45