Submission #1039797

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039797		doducanh	Commuter Pass (JOI18_commuter_pass)	C++14	15 / 100	886 ms	262144 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=1;i<=n;i++)arr[i]=inf;
    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(du>arr[u])continue;
        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)));
    dp[start][0]=du[start];
    dp[start][1]=dv[start];
    d[start]=0;
    while(q.size()){
        int u=q.top().se.fi;
        int duu=q.top().fi;
        int par=q.top().se.fi;
        q.pop();
        if(vst[u]==0){
            for(auto [v,w]:adj[u]){
                if(d[v]>=duu+w){
                    d[v]=duu+w;
                    dp[v][0]=min(dp[u][0],du[v]);
                    dp[v][1]=min(dp[u][1],dv[v]);
                    q.push(mp(d[v],mp(v,u)));
                }
            }
        }
    }
    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:30:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   30 |         for(auto [v,w]:adj[u]){
      |                  ^
commuter_pass.cpp: In function 'long long int dijkstra2(long long int, long long int)':
commuter_pass.cpp:57:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   57 |             for(auto [v,w]:adj[u]){
      |                      ^
commuter_pass.cpp:54:13: warning: unused variable 'par' [-Wunused-variable]
   54 |         int par=q.top().se.fi;
      |             ^~~
commuter_pass.cpp: At global scope:
commuter_pass.cpp:88:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   88 | main()
      | ^~~~

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