Submission #233694

#	Time	Username	Problem	Language	Result	Execution time	Memory
233694		Charis02	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	837 ms	68224 KiB

commuter_pass

#include<iostream>
#include<stdio.h>
#include<vector>
#include<cmath>
#include<queue>
#include<string.h>
#include<map>
#include<set>
#include<algorithm>
#define ll long long
#define pi pair < ll,ll >
#define mp(a,b) make_pair(a,b)
#define mid (low+high)/2
#define rep(i,a,b) for(int i = a;i < b;i++)
#define N 200004
#define INF 1e16

using namespace std;

ll n,m,s,t,u,v;
ll d[N][4];
vector < pi > graph[N];
vector < ll > par[N][4];
vector < ll > dag[N];
bool vis[N];
ll minvalue[N];

bool in_path(ll x)
{
    return (d[x][0]+d[x][1]==d[t][0]);
}

void dijkstra(int root,int id)
{
    rep(i,0,n+1)
    {
        d[i][id] = INF;
        par[i][id].clear();
    }

    priority_queue < pi > pq;
    pq.push(mp(0,root));
    d[root][id] = 0;

    while(!pq.empty())
    {
        pi cur = pq.top();
        pq.pop();
        cur.first*=-1;

        if(d[cur.second][id] < cur.first)
            continue;

        rep(i,0,graph[cur.second].size())
        {
            ll vv = graph[cur.second][i].first;
            ll cc = graph[cur.second][i].second;

            if(d[vv][id] > cur.first+cc)
            {
                d[vv][id]=cur.first+cc;
                par[vv][id].clear();
                pq.push(mp(-d[vv][id],vv));
            }
            if(d[vv][id]==cur.first+cc)
                par[vv][id].push_back(cur.second);
        }
    }

    return;
}

void construct_dag(ll id)
{
    rep(i,1,n+1)
    {
        rep(j,0,par[i][id].size())
        {
            dag[i].push_back(par[i][id][j]);
        }
    }

    return;
}

ll solve(ll cur)
{
    if(!in_path(cur))
        minvalue[cur] = INF;
    if(vis[cur] || !in_path(cur))
        return INF;

    vis[cur]=true;

    ll res = d[cur][2] + d[cur][3];
    minvalue[cur]=d[cur][3];

    rep(i,0,dag[cur].size())
    {
        ll vv = dag[cur][i];
        res = min(res,solve(vv));
        minvalue[cur] = min(minvalue[cur],minvalue[vv]);
    }

    res=min(res,d[cur][2]+minvalue[cur]);

    //cout << cur << " "<< res << "   " << minvalue[cur] << endl;

    return res;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    cin >> s >> t;
    cin >> u >> v;

    rep(i,0,m)
    {
        ll a,b,c;
        cin >> a >> b >> c;
        graph[a].push_back(mp(b,c));
        graph[b].push_back(mp(a,c));
    }

    dijkstra(s,0);
    construct_dag(0);
    dijkstra(t,1);
    dijkstra(u,2);
    dijkstra(v,3);

    ll ans = d[u][3];

    rep(x,1,n+1)
        ans = min(ans,solve(x));

    rep(i,1,n+1)
        vis[i]=false;

    dijkstra(u,3);
    dijkstra(v,2);

  //  cout << endl << endl << endl;

    rep(x,1,n+1)
        ans = min(ans,solve(x));

    cout << ans << endl;

    return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void dijkstra(int, int)':
commuter_pass.cpp:14:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,a,b) for(int i = a;i < b;i++)
commuter_pass.cpp:54:13:
         rep(i,0,graph[cur.second].size())
             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:54:9: note: in expansion of macro 'rep'
         rep(i,0,graph[cur.second].size())
         ^~~
commuter_pass.cpp: In function 'void construct_dag(long long int)':
commuter_pass.cpp:14:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,a,b) for(int i = a;i < b;i++)
commuter_pass.cpp:77:13:
         rep(j,0,par[i][id].size())
             ~~~~~~~~~~~~~~~~~~~~~   
commuter_pass.cpp:77:9: note: in expansion of macro 'rep'
         rep(j,0,par[i][id].size())
         ^~~
commuter_pass.cpp: In function 'long long int solve(long long int)':
commuter_pass.cpp:14:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,a,b) for(int i = a;i < b;i++)
commuter_pass.cpp:98:9:
     rep(i,0,dag[cur].size())
         ~~~~~~~~~~~~~~~~~~~         
commuter_pass.cpp:98:5: note: in expansion of macro 'rep'
     rep(i,0,dag[cur].size())
     ^~~

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