Submission #158813

#	Time	Username	Problem	Language	Result	Execution time	Memory
158813		janchomath	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	809 ms	41416 KiB

commuter_pass

#include<bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pb push_back
#define N 200005
#define mp make_pair
using namespace std;
ll ds[N],dt[N],du[N],df[N],raod[N],s,t,u,f,n,m,dp1[N],dp2[N],p[N],ans=100000000000000;
vector<pair<ll,ll> >v[N];
vector<ll>g[N],rev[N];
void dj(ll k){
	vector<ll> d (n + 1, 100000000000000);
	d[k] = 0;
	set < pair<ll,ll> > q;
	q.insert (make_pair (d[k], k));
	while(!q.empty()) {
		ll x = q.begin()->s;
		q.erase (q.begin());
		for (int i=0; i<v[x].size(); i++) {
			ll to = v[x][i].f,
				len = v[x][i].s;
			if (d[x] + len < d[to]) {
				if(q.find(mp(d[to] , to)) != q.end())q.erase(make_pair (d[to], to));
				d[to] = d[x] + len;
				q.insert(make_pair (d[to], to));
			}
		}
	}
    for(int i=1; i<=n; i++){
        p[i] = d[i];
     }
}
void dfs(ll x){
    dp1[x] = 100000000000000;
    dp2[x] = 100000000000000;
    for(int i=0; i<rev[x].size(); i++)
        dp1[x] = min(dp1[x] , dp1[rev[x][i]]);
    dp1[x] = min(dp1[x] , du[x]);
    ans = min(ans , dp1[x] + df[x]);
    for(int i=0; i<rev[x].size(); i++)
        dp2[x] = min(dp2[x] , dp2[rev[x][i]]);
    dp2[x] = min(dp2[x] , df[x]);
    ans = min(ans , dp2[x] + du[x]);
    for(int i=0; i<g[x].size(); i++)
        if(raod[g[x][i]] <= 1)dfs(g[x][i]);
        else raod[g[x][i]]--;
}
int main(){
    ios::sync_with_stdio(false);
    cin >> n >> m >> s >> t >> u >> f;
    
    for(int i=1; i<=m; i++){
        int x,y,z;
        cin >> x >> y >> z;
        v[x].pb(mp(y , z));
        v[y].pb(mp(x , z));
    }
    
    dj(s);
    for(int i=1; i<=n; i++)
        ds[i] = p[i];
    dj(t);
    for(int i=1; i<=n; i++)
        dt[i] = p[i];
    dj(u);
    for(int i=1; i<=n; i++)
        du[i] = p[i];
    dj(f);
    for(int i=1; i<=n; i++)
        df[i] = p[i];
    for(int i=1; i<=n; i++)
        for(int j=0; j<v[i].size(); j++)
            if(ds[i] + v[i][j].s + dt[v[i][j].f] == ds[t]){
                g[i].pb(v[i][j].f),
                rev[v[i][j].f].pb(i);
            }
    for(int i=1; i<=n; i++)
        raod[i] = (ll)rev[i].size();
    ans = du[f];
    dfs(s);
    
    cout << ans << endl;
    
    
    return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void dj(long long int)':
commuter_pass.cpp:20:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i=0; i<v[x].size(); i++) {
                 ~^~~~~~~~~~~~
commuter_pass.cpp: In function 'void dfs(long long int)':
commuter_pass.cpp:37:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<rev[x].size(); i++)
                  ~^~~~~~~~~~~~~~
commuter_pass.cpp:41:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<rev[x].size(); i++)
                  ~^~~~~~~~~~~~~~
commuter_pass.cpp:45:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<g[x].size(); i++)
                  ~^~~~~~~~~~~~
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:73:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0; j<v[i].size(); j++)
                      ~^~~~~~~~~~~~

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