Submission #1307515

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307515		ng.annhaat	Commuter Pass (JOI18_commuter_pass)	C++20	15 / 100	216 ms	39064 KiB

commuter_pass

/*
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
░░░░░░░  ░░░░░░░░   ░░░░░   ░           ░   ░░░░   ░░░░░     ░░░░░░        ░░░░
▒▒▒▒▒▒  ▒  ▒▒▒▒▒▒   ▒▒▒▒▒   ▒▒▒▒▒   ▒▒▒▒▒   ▒▒▒▒   ▒▒▒   ▒▒▒▒   ▒▒▒   ▒▒▒▒   ▒▒
▒▒▒▒▒  ▒▒   ▒▒▒▒▒   ▒▒▒▒▒   ▒▒▒▒▒   ▒▒▒▒▒   ▒▒▒▒   ▒   ▒▒▒▒▒▒▒▒   ▒   ▒▒▒▒   ▒▒
▓▓▓▓   ▓▓▓   ▓▓▓▓   ▓▓▓▓▓   ▓▓▓▓▓   ▓▓▓▓▓          ▓   ▓▓▓▓▓▓▓▓   ▓  ▓   ▓▓▓▓▓▓
▓▓▓       ▓   ▓▓▓   ▓▓▓▓▓   ▓▓▓▓▓   ▓▓▓▓▓   ▓▓▓▓   ▓   ▓▓▓▓▓▓▓▓   ▓   ▓▓   ▓▓▓▓
▓▓   ▓▓▓▓▓▓▓   ▓▓   ▓▓▓▓▓   ▓▓▓▓▓   ▓▓▓▓▓   ▓▓▓▓   ▓▓▓   ▓▓▓▓▓   ▓▓   ▓▓▓▓   ▓▓
█   █████████   ███      ████████   █████   ████   █████     ██████   ██████
███████████████████████████████████████████████████████████████████████████████

         ▄▄▄      ███▄    █  ███▄    █   ██░ ██  ▄▄▄      ▄▄▄     ▄▄▄█████▓
        ▒████▄    ██ ▀█   █  ██ ▀█   █ ▒▓██░ ██ ▒████▄   ▒████▄   ▓  ██▒ ▓▒
        ▒██  ▀█▄ ▓██  ▀█ ██▒▓██  ▀█ ██▒░▒██▀▀██ ▒██  ▀█▄ ▒██  ▀█▄ ▒ ▓██░ ▒░
        ░██▄▄▄▄██▓██▒  ▐▌██▒▓██▒  ▐▌██▒ ░▓█ ░██ ░██▄▄▄▄██░██▄▄▄▄██░ ▓██▓ ░
         ▓█   ▓██▒██░   ▓██░▒██░   ▓██░ ░▓█▒░██▓ ▓█   ▓██ ▓█   ▓██  ▒██▒ ░
         ▒▒   ▓▒█░ ▒░   ▒ ▒ ░ ▒░   ▒ ▒   ▒ ░░▒░▒ ▒▒   ▓▒█ ▒▒   ▓▒█  ▒ ░░
          ░   ▒▒ ░ ░░   ░ ▒░░ ░░   ░ ▒░  ▒ ░▒░ ░  ░   ▒▒   ░   ▒▒     ░
          ░   ▒     ░   ░ ░    ░   ░ ░   ░  ░░ ░  ░   ▒    ░   ▒    ░ ░
              ░           ░          ░   ░  ░  ░      ░        ░


*/
//#include <bits/BaoMinhTranc++.h>
#include <bits/stdc++.h>
#define int int64_t
//#define ll int64_t
#define ld long double
#define ii pair<int,int>
#define iii pair<int,ii>
#define fi first
#define se second
#define ALL(x) x.begin(),x.end()
#define ALLr(x) x.rbegin(),x.rend()
#define upgrade ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define name "youreagoodmanarthur"
using namespace std;
const int Max=1<<20;
const int N=1e5+3;
const int INF=1e18;
const int MOD=998244353;
const int MOD2=1e9+8;
const int base=26;
const int LOG=32;
template<class X,class Y>
    bool minimize(X& x,const Y& y)
    {
        if(x>y){
            x=y;
            return 1;
        }return 0;
    }
template<class X,class Y>
    bool maximize(X& x,const Y& y)
    {
        if(x<y){
            x=y;
            return 1;
        }return 0;
    }
int n,m,s,t,u,v;
vector<ii> g[N];
priority_queue<ii,vector<ii>,greater<ii>> q;
int dist[3][N];
vector<int> tail[3][N];
vector<int> dag;
vector<int> g_dag[N];
bool visited[N];
ii dp[N];
void dijk(int st,int slot)
{
    for(int i=1;i<=n;i++)dist[slot][i]=INF;
    dist[slot][st]=0;
    q.push({0,st});
    while(!q.empty()){
        int u=q.top().se,cost=q.top().fi;
        q.pop();
        if(dist[slot][u]<cost)continue;
        for(ii x:g[u]){
            int v=x.fi,w=x.se;
            if(minimize(dist[slot][v],cost+w)){
                tail[slot][v].clear();
                q.push({cost+w,v});
            }
            if(cost+w == dist[slot][v])tail[slot][v].push_back(u);
        }
    }
}
void build()
{
    dag.push_back(t);
    queue<int> sontung;
    sontung.push(t);
    visited[t]=1;
    while(!sontung.empty()){
        int x=sontung.front();
        sontung.pop();
        for(int y:tail[0][x]){
            g_dag[y].push_back(x);
            if(!visited[y]){
                dag.push_back(y);
                visited[y]=1;
                sontung.push(y);
            }
        }
    }
}
void solve()
{
    cin>>n>>m;
    cin>>s>>t;
    cin>>u>>v;
    for(int _=1;_<=m;_++){
        int x,y,w;cin>>x>>y>>w;
        g[x].push_back({y,w});
        g[y].push_back({x,w});
    }
    dijk(s,0);dijk(u,1);dijk(v,2);
    build();
    int ans=dist[1][v];
    for(int x:dag){
        dp[x]={dist[1][x],dist[2][x]};
        for(int y:g_dag[x]){
            minimize(ans,dist[1][x]+dp[y].se);
            minimize(ans,dist[2][x]+dp[y].fi);
            minimize(dp[x].fi,dp[y].fi);
            minimize(dp[x].se,dp[y].se);
        }
    }
    cout<<ans;
}
void prepare()
{

}
signed main()
{
    upgrade
    if(fopen(name".INP","r")){
        freopen(name".INP","r",stdin);
        freopen(name".OUT","w",stdout);
    }
    prepare();
    int test=1;
//    cin>>test;
    while(test--)solve();
    return 0;
}
/*

                                                                                                       ░▓▓
                                                                 ░▒▒▒         ░▒▒▒▒▒▒░░░               ░▓▓
▓▒        ▒▓▓▓▓▓▓▓▓▓▓▓▓▒                  ░▓▓▓▓▓▓▓▓▓▓▓▒░       ▒▓▓▒      ▒▒▒▒░   ░░░░▒░▒▒▒▒▒▒          ░▓▓    ░░▒▒▒▒▒░░
▒▓▓▒   ▒▓▓░            ░▓▓▒           ░▓▓▓▒            ░▒▓▓░░▓▓▒      ▒▒▒  ▒▒▒▒▒▒░░░▒▒▒▒▒▒▒▒▒▒▒░       ░▓▓▓▒▒▒▒▒▒▒▒▒▒▓▒▒░
   ▓▓▓▓▒                 ░▓▓▒       ▒▓▓▒                 ░▓▓▓░      ░▒░        ░▒▒▒▒▒▒▒▒  ▒▒▒░ ▒▒▒     ░▓▓
                          ░▓▓░     ▓▓▓                                                 ░▒▒▒ ▒▒▒ ░▒▒    ▒▓▒
                           ▒▓▒    ▓▓▓                                      ░░            ▒▒░ ▒▒▒ ▒▒░   ▓▓▓
                           ░▓▒   ░▓▓▓                                  ░▒  ▒▒░           ▒▒░ ▒▒░ ▒▒▒   ▓▓▓░
                           ░▓▒   ░▓▓▓▒                                 ▒▒▒ ░▒▒▒░       ░▒▒░ ░▒▒ ▒▒▒    ▓▓▓▒
                           ▒▓▒     ▓▓▓░                      ░      ▒▒░  ▒▒▒   ▒▒▒▒▒▒▒▒░  ▒▒▒▒▒▒▒▒     ░▓▓▓
                          ░▓▓▒      ▒▓▓▓▒                 ░▓▓▓▓▒     ░▒▒   ░▒▒▒▒▒▒▒▒▒▒▒▒▒▒░ ▒▒▒░        ░▓▓▓
                           ░▒         ░▓▓▓▓▓▓▒░       ▒▓▓▓▓▓▒▓▓▒        ▒▒▒▒▒▒▒░    ░▒▒▒▒▒▒▒░             ▓▓▓▓▒▒       ▒▓▓▓▓
                                           ░░▓▓▓▓▓▓▓▓▒░░     ▒▓▒                 ░▒▒▒▒░                       ░▒▓▓▓▓▓▓▓▓▒░
                                                             ▒▓▓░                  ▒▒░
                            ▓▒                               ▒▓▓░                  ▒▒▒░
                            ▓▓▒                             ░▓▓▒                  ░▒▒▒▒
                             ▓▓▓░                          ▒▓▓▓                    ░▒▒▒
                               ░▓▓▓▓░                   ░▓▓▓▒
                                   ░▓▓▓▓▓▒▒░░░  ░░░▒▒▓▓▓▓░
                                         ░▒▒▒▒▒▒▒▒░
*/

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:140:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  140 |         freopen(name".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:141:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  141 |         freopen(name".OUT","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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