Submission #229868

#	Time	Username	Problem	Language	Result	Execution time	Memory
229868		davooddkareshki	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	775 ms	33496 KiB

commuter_pass

// be name khoda
#include<bits/stdc++.h>
 
using namespace std;
 
#define F first
#define S second
//#define mp make_pair 
typedef long long ll;
#define int long long
#pragma GCC optimize("Ofast")
 
const int maxn = 2e5+10;
const int mod = 1e9+7;
const ll inf = 1e18+10;
//const int N = 2e6+10;
 
int n, m, k;
int a[maxn], b[maxn], dis[maxn], D[maxn];
int Ss, T, U, V;
vector<pair<int,int>> g[maxn];
vector<int> g2[maxn];

void dijkstra(int s, char tp)
{
   // cout<< s <<" ";
    fill(D,D+maxn,inf);
    set<pair<int,int>> se;
    D[s] = 0;
    se.insert({0,s});

    while(se.size())
    {
        int v = se.begin()->S;
        se.erase({D[v],v});
      //  cout<< v <<" ";
        for(auto e : g[v])
        {
            int u = e.F, w = e.S;
            if(D[v] + w < D[u])
            {
                se.erase({D[u],u});
                D[u] = D[v] + w;
                se.insert({D[u],u});
            }
        }
    }

    if(tp == 'S')
        for(int i = 1; i <= n; i++) dis[i] = D[i];
    if(tp == 'V')
        for(int i = 1; i <= n; i++) a[i] = D[i];
    if(tp == 'U')
        for(int i = 1; i <= n; i++) b[i] = D[i];
}

bool mark[maxn];
int mn[maxn], mn2[maxn];
ll ans = inf;
void dfs(int v)
{
    mn[v] = b[v];
    mn2[v] = a[v];
    mark[v] = 1;
    for(auto u : g2[v])
        if(!mark[u])
        {
            dfs(u);
            mn[v] = min(mn[v],mn[u]);
            mn2[v] = min(mn2[v],mn2[u]);
        }
        else
        {
            mn[v] = min(mn[v],mn[u]);
            mn2[v] = min(mn2[v],mn2[u]);
        }
    ans = min(ans,a[v]+mn[v]);
    ans = min(ans,b[v]+mn2[v]);
    //cout<< v <<" "<< mn[v] <<" "<< mn2[v] <<" "<< a[v] <<" "<< b[v] <<"\n";
}

signed main()
{
   // ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    cin>> n >> m >> Ss >> T >> U >> V;
    //cout<<"SDFg";
    for(int i = 1; i <= m; i++)
    {
        int u, v, w; cin>> u >> v >> w;
   //     cout<< i <<" ";
        g[u].push_back({v,w});
        g[v].push_back({u,w});
    }
  //  cout<<"SDFG";

    dijkstra(Ss,'S');
    dijkstra(U,'U');
    dijkstra(V,'V');

    for(int v = 1; v <= n; v++)
    {
        for(auto e : g[v])
        {
            int u = e.F, w = e.S;
            if(dis[v] == dis[u] + w)
            {
                g2[v].push_back(u);
               // cout<< u <<" "<< v <<"\n";
            }
        }
        //cout<< a[v] <<" "<< b[v] <<" "<< dis[v] <<"\n";
    }
    dfs(T);
    cout<< min(ans,a[U]);
}

/*
6 6
1 6
1 4
1 2 1
2 3 1
3 5 1
2 4 3
4 5 2
5 6 1

6 5
1 2
3 6
1 2 1000000000
2 3 1000000000
3 4 1000000000
4 5 1000000000
5 6 1000000000

8 8
5 7
6 8
1 2 2
2 3 3
3 4 4
1 4 1
1 5 5
2 6 6
3 7 7
4 8 8

5 5
1 5
2 3
1 2 1
2 3 10
2 4 10
3 5 10
4 5 10

10 15
6 8
7 9
2 7 12
8 10 17
1 3 1
3 8 14
5 7 15
2 3 7
1 10 14
3 6 12
1 5 10
8 9 1
2 9 7
1 4 1
1 8 1
2 4 7
5 6 16
*/

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