Submission #1039818

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039818		doducanh	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	267 ms	33720 KiB

commuter_pass

///breaker
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define ii pair<int,int>
#define iii pair<int,ii>
#define mp make_pair
const int inf=1e18+7;
const int maxn=1e5+7;
int du[maxn];
int dv[maxn];
vector<ii>adj[maxn];
int n,m,s,t,u,v;
int dp[maxn][2];
int vst[maxn];
int d[maxn];
void dijkstra1(int start,int arr[])
{
    for(int i=0;i<=n;i++){
        arr[i]=inf;
        vst[i]=0;
    }
    arr[start]=0;
    priority_queue<ii,vector<ii>,greater<ii>>q;
    q.push(mp(0,start));
    while(q.size()){
        int u=q.top().se;
        int du=q.top().fi;
        q.pop();
        if(vst[u])continue;
        vst[u]=1;
        for(auto [v,w]:adj[u]){
            if(arr[v]>du+w){
                arr[v]=du+w;
                q.push({arr[v],v});
            }
        }
    }
}
int dijkstra2(int start,int endd)
{
    for(int i=0;i<=n;i++){
        d[i]=inf;
        dp[i][0]=inf;
        dp[i][1]=inf;
        vst[i]=0;
    }
    priority_queue<iii,vector<iii>,greater<iii>>q;
    q.push(mp(0,mp(start,0)));
    d[start]=0;
    while(q.size()){
        int u=q.top().se.fi;
        int duu=q.top().fi;
        int par=q.top().se.se;
        q.pop();
        if(vst[u]==0){
            vst[u]=1;
            dp[u][0]=min(dp[par][0],du[u]);
            dp[u][1]=min(dp[par][1],dv[u]);
            d[u]=duu;
            for(auto [v,w]:adj[u]){
                q.push(mp(duu+w,mp(v,u)));
            }
        }
        else if(duu==d[u]){
            if(min(du[u],dp[par][0])+min(dv[u],dp[par][1])<=dp[u][0]+dp[u][1]){
                dp[u][0]=min(du[u],dp[par][0]);
                dp[u][1]=min(dv[u],dp[par][1]);
            }
        }
    }
    return dp[endd][0]+dp[endd][1];
}
void sol(){

    cin>>n>>m;
    cin>>s>>t;
    cin>>u>>v;
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        adj[u].push_back({v,w});
        adj[v].push_back({u,w});
    }
    dijkstra1(u,du);
    int ans=du[v];
    dijkstra1(v,dv);
    ans=min(ans,dijkstra2(s,t));
    ans=min(ans,dijkstra2(t,s));
    cout<<ans;

}
main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t=1;
    while(t--){
        sol();
    }
    // you should actually read the stuff at the bottom
    return 0;
}
/* stuff you should look for
 * int overflow, array bounds
 * special cases (n=1?)
 * do smth instead of nothing and stay organized
 * WRITE STUFF DOWN
 * DON'T GET STUCK ON ONE APPROACH
 */

Compilation message (stderr)

commuter_pass.cpp: In function 'void dijkstra1(long long int, long long int*)':
commuter_pass.cpp:34:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   34 |         for(auto [v,w]:adj[u]){
      |                  ^
commuter_pass.cpp: In function 'long long int dijkstra2(long long int, long long int)':
commuter_pass.cpp:63:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   63 |             for(auto [v,w]:adj[u]){
      |                      ^
commuter_pass.cpp: At global scope:
commuter_pass.cpp:95:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   95 | main()
      | ^~~~

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