Submission #1039435

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039435		2zzz	Commuter Pass (JOI18_commuter_pass)	C++14	0 / 100	2100 ms	43844 KiB

commuter_pass

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ii pair<int,int>
#define pii pair<int,ii>
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define RUN_FAST ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int N = 1e6+5;
const int M = log2(N)+5;
const ll oo = 1e18;
const int maxn = 5010;
const ll mod = 1000000007;
const int base = 311;
int n, m, s, t, u, v;
int dis[3][N], best[N][3];
vector<ii> g[N];
int ans;
void dijk(int start, int type)
{
    for(int i = 1; i <= n; i++)
    {
        dis[type][i] = 1e9;
    }
    dis[type][start] = 0;
    priority_queue<ii, vector<ii>, greater<ii> > q;
    q.push({dis[type][start], start});
    while(!q.empty())
    {
        int u = q.top().se;
        int cost = q.top().fi;
        q.pop();
        if(cost > dis[type][u]) continue;
        for(auto it : g[u])
        {
            int v = it.fi;
            int w = it.se;
            if(dis[type][v] > dis[type][u] + w)
            {
                dis[type][v] = dis[type][u] + w;
                q.push({dis[type][v], v});
            }
        }
    }
}
void dfs(int t)
{
    best[t][0] = dis[1][t];
    best[t][1] = dis[2][t];
//    cout << best[t][1] << " " << best[t][0] << '\n';
    for(auto it : g[t])
    {
        int v = it.fi;
        int w = it.se;
        if(dis[0][v] + w != dis[0][t]) continue;
        dfs(v);
//        cout << best[t][0] << " " << best[v][0] << " " << best[t][1] << " " << best[v][1] << '\n';
        best[t][0] = min(best[t][0], best[v][0]);
        best[t][1] = min(best[t][1], best[v][1]);
    }
    ans = min(ans, dis[1][t] + best[t][1]);
    ans = min(ans, dis[2][t] + best[t][0]);
}
int main()
{
    RUN_FAST
//    freopen("test.inp","r",stdin);
//    freopen("test.out","w",stdout);
    cin >> n >> m >> s >> t >> u >> v;
    for(int i = 1; i <= m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].pb({v, w});
        g[v].pb({u, w});
    }
    dijk(s, 0);
    dijk(u, 1);
    dijk(v, 2);
    ans = dis[1][v];
    dfs(t);
    cout << ans;
    return 0;
}
// 2zzz;
// codelozd
//⣿⣿⣿⡇⢩⠘⣴⣿⣥⣤⢦⢁⠄⠉⡄⡇⠛⠛⠛⢛⣭⣾⣿⣿⡏
//⣿⣿⣿⡇⠹⢇⡹⣿⣿⣛⣓⣿⡿⠞⠑⣱⠄⢀⣴⣿⣿⣿⣿⡟
//⣿⣿⣿⣧⣸⡄⣿⣪⡻⣿⠿⠋⠄⠄⣀⣀⢡⣿⣿⣿⣿⡿⠋
//⠘⣿⣿⣿⣿⣷⣭⣓⡽⡆⡄⢀⣤⣾⣿⣿⣿⣿⣿⡿⠋
//⠄⢨⡻⡇⣿⢿⣿⣿⣭⡶⣿⣿⣿⣜⢿⡇⡿⠟⠉
//⠄⠸⣷⡅⣫⣾⣿⣿⣿⣷⣙⢿⣿⣿⣷⣦⣚⡀
//⠄⠄⢉⣾⡟⠙❤️⠈⢻⣿⣷⣅⢻⣿⣿⣿⣿⣿⣶⣶⡆⠄⡀
//⠄⢠⣿⣿⣧⣀⣀⣀⣀⣼⣿⣿⣿⡎⢿⣿⣿⣿⣿⣿⣿⣇❤️⠄
//⠄⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢇⣎⢿⣿⣿⣿⣿⣿⣿⣿⣶⣶
//⠄⠄⠻⢿⣿⣿⣿⣿⣿⣿⣿⢟⣫⣾⣿⣷⡹⣿⣿⣿⣿⣿⣿⣿⡟
//⠄⠄⠄⠄⢮⣭⣍⡭⣭⡵⣾⣿⣿⣿⡎⣿⣿⣌⠻⠿⠿⠿⠟⠋
//⠄⠄⠄⠄⠈⠻⣿⣿⣿⣿⣹⣿⣿⣿⡇⣿⣿⡿
//⠄⠄⣀⣴⣾⣶⡞⣿⣿⣿⣿⣿⣿⣿⣾⣿⡿⠃
//⣠⣾⣿⣿⣿⣿⣿⣹⣿⣿⣿⣿⣿⡟⣹⣿⣳⡄

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