Submission #635675

#	Time	Username	Problem	Language	Result	Execution time	Memory
635675		PoonYaPat	Commuter Pass (JOI18_commuter_pass)	C++14	Compilation error	0 ms	0 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
typedef tuple<ll,ll,ll> t;

ll n,m,st,u,v,en,ans=LLONG_MAX;
ll ds[100001],du[100001],dv[100001];
vector<pii> adj[100001];
vector<int> adj2[100001];
priority_queue<pii, vector<pii>, greater<pii>> q;
priority_queue<t, vector<t>, greater<t>> pq;

void dij(ll *dis, int start) {
    bool vis[100001];
    memset(vis,0,sizeof(vis));
    for (int i=1; i<=n; ++i) dis[i]=LLONG_MAX;

    dis[start]=0;
    q.push({0,start});

    while (!q.empty()) {
        pii a=q.top();
        q.pop();

        ll node=a.second;

        if (vis[node]) continue;
        vis[node]=true;

        for (auto s : adj[node]) {
            ll des=s.first, w=s.second;
            if (dis[des]>dis[node]+w) {
                dis[des]=dis[node]+w;
                q.push({dis[des],des});
            }
        }
    }
}

void dij2(ll *dis, int start) {
    bool vis[100001];
    memset(vis,0,sizeof(vis));
    for (int i=1; i<=n; ++i) dis[i]=LLONG_MAX;

    dis[start]=0;
    pq.push({0,start,0});

    while (!pq.empty()) {
        ll node, par, d;
        tie (d,node,par)=pq.top();
        pq.pop();

        if (dis[node]=d) adj2[node].push_back(par);

        if (vis[node]) continue;
        vis[node]=true;

        for (auto s : adj[node]) {
            ll des=s.first, w=s.second;
            if (dis[des]>=dis[node]+w) {
                dis[des]=dis[node]+w;
                pq.push({dis[des],des,node});
            }
        }
    }
}

multiset<ll> udis,vdis;
int cnt;

void dfs(int x) {
    ++cnt;
    if (cnt>n) return 1;
    udis.insert(du[x]);
    vdis.insert(dv[x]);

    if (x==st) ans=min(ans,*(udis.begin())+*(vdis.begin()));
    for (auto s : adj2[x]) dfs(s);

    udis.erase(udis.find(du[x]));
    vdis.erase(vdis.find(dv[x]));

}

void dfs2(int x) {
    ans=min(ans,dv[x]);
    for (auto s : adj2[x]) dfs2(s);
}


int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n>>m>>st>>en>>u>>v;
    for (int i=0; i<m; ++i) {
        ll a,b,w;
        cin>>a>>b>>w;
        adj[a].push_back(pii(b,w));
        adj[b].push_back(pii(a,w));
    }
    dij(du,u);
    dij(dv,v);

    if (st==u) {
        dfs2(en);
        cout<<min(ans,du[v]);
    }

    dij2(ds,st);
    dfs(en);
    cout<<min(ans,du[v]);
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void dij2(ll*, int)':
commuter_pass.cpp:54:22: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   54 |         if (dis[node]=d) adj2[node].push_back(par);
      |             ~~~~~~~~~^~
commuter_pass.cpp: In function 'void dfs(int)':
commuter_pass.cpp:74:23: error: return-statement with a value, in function returning 'void' [-fpermissive]
   74 |     if (cnt>n) return 1;
      |                       ^