Submission #103529

#	Time	Username	Problem	Language	Result	Execution time	Memory
103529		Alliance	Commuter Pass (JOI18_commuter_pass)	C++14	31 / 100	1071 ms	28964 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,ll>> g[MAX_N];
ll dis[MAX_N];
int mark[MAX_N];
vector<int> p[MAX_N];
int s,t,u,v;
vector<int> vers;
int n,m;

void dij()
{
    for(int i = 1;i<=n;++i)
        dis[i] = 1e18;
    for(auto x:vers)
        dis[x] = 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])
        {
            ll u = x.first;
            int w = x.second;
            ll d = dis[v]+w;
            if (dis[u]==d)
                p[u].push_back(v);
            else if (dis[u]>d)
            {
                st.erase({dis[u],u});
                dis[u] = d;
                st.insert({dis[u],u});
                p[u].clear();
                p[u].push_back(v);
            }
        }
    }
}

void dfs(int v)
{
    mark[v]++;
    vers.push_back(v);
    for(auto x:p[v])
    {
        if (!mark[x])
            dfs(x);
    }
}

void make_zero(int u,int v)
{
    for(int i = 0;i<g[u].size();++i)
    {
        if (g[u][i].first==v)
            g[u][i].second = 0;
    }
    for(int i = 0;i<g[v].size();++i)
    {
        if (g[v][i].first==u)
            g[v][i].second = 0;
    }
}

int main()
{
    cin >> n >> m >> s >> t >> u >> v;
    for(int i = 0;i<m;++i)
    {
        int a,b,w;
        scanf("%d%d%d",&a,&b,&w);
        g[a].push_back({b,w});
        g[b].push_back({a,w});
    }
    vers.push_back(s);
    dij();
    vers.clear();
    if (s==u)
    {
        dfs(t);
        dij();
        cout << dis[v];
        return 0;
    }
    vector<int> path;
    int now = t;
    while(p[now].size())
    {
        path.push_back(now);
        now = p[now][0];
    }
    path.push_back(now);
    for(int i = 0;i<path.size()-1;++i)
        make_zero(path[i],path[i+1]);
    vers.push_back(u);
    dij();
    cout << dis[v];
    return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void make_zero(int, int)':
commuter_pass.cpp:62:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i<g[u].size();++i)
                   ~^~~~~~~~~~~~
commuter_pass.cpp:67:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i<g[v].size();++i)
                   ~^~~~~~~~~~~~
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:102:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i<path.size()-1;++i)
                   ~^~~~~~~~~~~~~~
commuter_pass.cpp:80:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d",&a,&b,&w);
         ~~~~~^~~~~~~~~~~~~~~~~~~

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