Submission #158811

# Submission time Handle Problem Language Result Execution time Memory
158811 2019-10-18T21:01:49 Z janchomath Commuter Pass (JOI18_commuter_pass) C++14
16 / 100
863 ms 39616 KB
#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,dp[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];
    //    cout << p[i] << " ";
     }
//     cout << endl;
}
void dfs(ll x){
    //cout << x << " " << rev[x].size() << endl;
    dp[x] = 100000000000000;
    for(int i=0; i<rev[x].size(); i++)
        dp[x] = min(dp[x] , dp[rev[x][i]]);
    dp[x] = min(dp[x] , du[x]);
    ans = min(ans , dp[x] + df[x]);
    //cout << dp[x] << " " << df[x] << "\n\n";
    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);
                //cout << i << "<-->" << v[i][j].f << endl;
            }
    for(int i=1; i<=n; i++)
        raod[i] = (ll)rev[i].size();
    ans = du[f];
//    cout << du[f] << " " << f << " " << u << endl;
    dfs(s);
    
    cout << ans << endl;
    
    
    return 0;
}

Compilation message

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:39:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<rev[x].size(); i++)
                  ~^~~~~~~~~~~~~~
commuter_pass.cpp:44: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:72:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0; j<v[i].size(); j++)
                      ~^~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 688 ms 35768 KB Output is correct
2 Correct 618 ms 35120 KB Output is correct
3 Correct 587 ms 39616 KB Output is correct
4 Correct 553 ms 35504 KB Output is correct
5 Correct 507 ms 36572 KB Output is correct
6 Correct 670 ms 35768 KB Output is correct
7 Correct 610 ms 37084 KB Output is correct
8 Correct 650 ms 36652 KB Output is correct
9 Correct 661 ms 35164 KB Output is correct
10 Correct 490 ms 35600 KB Output is correct
11 Correct 230 ms 30816 KB Output is correct
12 Correct 684 ms 34980 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 652 ms 36020 KB Output is correct
2 Correct 863 ms 36288 KB Output is correct
3 Correct 782 ms 35668 KB Output is correct
4 Incorrect 779 ms 36008 KB Output isn't correct
5 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 16376 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 688 ms 35768 KB Output is correct
2 Correct 618 ms 35120 KB Output is correct
3 Correct 587 ms 39616 KB Output is correct
4 Correct 553 ms 35504 KB Output is correct
5 Correct 507 ms 36572 KB Output is correct
6 Correct 670 ms 35768 KB Output is correct
7 Correct 610 ms 37084 KB Output is correct
8 Correct 650 ms 36652 KB Output is correct
9 Correct 661 ms 35164 KB Output is correct
10 Correct 490 ms 35600 KB Output is correct
11 Correct 230 ms 30816 KB Output is correct
12 Correct 684 ms 34980 KB Output is correct
13 Correct 652 ms 36020 KB Output is correct
14 Correct 863 ms 36288 KB Output is correct
15 Correct 782 ms 35668 KB Output is correct
16 Incorrect 779 ms 36008 KB Output isn't correct
17 Halted 0 ms 0 KB -