Submission #103531

#	Time	Username	Problem	Language	Result	Execution time	Memory
103531		Alliance	Commuter Pass (JOI18_commuter_pass)	C++14	15 / 100	1682 ms	30200 KiB

commuter_pass

// In the name of Allah. Ya ali!
#include<bits/stdc++.h>
#define double long double
typedef long long ll;
const ll MAX_N = 1e5+10;
const ll MOD = 1e9+7;
using namespace std;

vector<pair<int,int>> g[MAX_N];
vector<int> p[MAX_N];
vector<int> pr[MAX_N];
ll dis[MAX_N];
ll m1[MAX_N];
ll d1[MAX_N];
ll d2[MAX_N];
ll m2[MAX_N];
int mark[MAX_N];
int n,m,s,t,u,v;
ll ans = 1e18;

void dij(int start)
{
    for(int i = 1;i<=n;++i)
        dis[i] = 1e18;
    dis[start] = 0;
    set<pair<ll,int>> st;
    for(int i = 1;i<=n;++i)
        st.insert({dis[i],i});
    while(st.size())
    {
        int v = (*st.begin()).second;
        st.erase(st.begin());
        for(auto x:g[v])
        {
            int u = x.first;
            ll d = dis[v]+x.second;
            if (dis[u]==d)
                p[u].push_back(v);
            else if (dis[u]>d)
            {
                p[u].clear();
                p[u].push_back(v);
                st.erase({dis[u],u});
                dis[u] = d;
                st.insert({dis[u],u});
            }
        }
    }
}

void bfs(int v)
{
    vector<int> q;
    q.push_back(v);
    mark[v]++;
    for(int i = 0;i<q.size();++i)
    {
        int u = q[i];
        ans = min(ans,min(m1[u]+d2[u],m2[u]+d1[u]));
        for(auto x:pr[u])
        {
            m1[x] = min(m1[x],m1[u]);
            m2[x] = min(m2[x],m2[u]);
            if (!mark[x])
            {
                q.push_back(x);
                mark[x]++;
            }
        }
    }
}

int main()
{
    cin >> n >> m >> s >> t >> u >> v;
    for(int i = 1;i<=m;++i)
    {
        int u,v,w;
        cin >> u >> v >> w;
        g[u].push_back({v,w});
        g[v].push_back({u,w});
    }
    dij(s);
    for(int i = 1;i<=n;++i)
        pr[i] = p[i];
    dij(u);
    for(int i = 1;i<=n;++i)
        d1[i] = m1[i] = dis[i];
    dij(v);
    for(int i = 1;i<=n;++i)
        d2[i] = m2[i] = dis[i];
    ans = dis[u];
    bfs(t);
    cout << ans;
    return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void bfs(int)':
commuter_pass.cpp:56:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i<q.size();++i)
                   ~^~~~~~~~~

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