Submission #229862

#	Time	Username	Problem	Language	Result	Execution time	Memory
229862		davooddkareshki	Commuter Pass (JOI18_commuter_pass)	C++17	0 / 100	730 ms	27640 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 = 1e5+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];
ll ans = inf;
void dfs(int v)
{
    mn[v] = b[v];
    mark[v] = 1;
    for(auto u : g2[v])
        if(!mark[u])
        {
            dfs(u);
            mn[v] = min(mn[v],mn[u]);
        }
    ans = min(ans,a[v]+mn[v]);
    //cout<< ctn[v] <<" ";
}

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<< ans;
}

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

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