제출 #635672

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
635672		PoonYaPat	Commuter Pass (JOI18_commuter_pass)	C++14	0 / 100	2074 ms	30204 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;

void dfs(int x) {
    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]));

}


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);
    dij2(ds,st);
    dfs(en);
    cout<<min(ans,du[v]);
}

컴파일 시 표준 에러 (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);
      |             ~~~~~~~~~^~

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