oj.uz

Submission #477147

# Submission time Handle Problem Language Result Execution time Memory
477147 2021-09-30T21:15:38 Z Qw3rTy Commuter Pass (JOI18_commuter_pass) C++11
100 / 100
 1303 ms 112540 KB 
/*
 * Key Observation: 只能顺着S->T走一段免费的或者逆着S->T走一段免费的; 不可能顺着+逆着，否则这一定不是S->T的最短路的一部分
 */
#include <bits/stdc++.h>
#define int long long
#define INF 1e16
#define pi pair<int,int>
#define fi first
#define se second
#define pb push_back
using namespace std;
const int maxN = 2e5+5;
struct cmp{
    bool operator() (pi a, pi b){
        return a.fi > b.fi;
    }
};
int N,M,S,T,U,V,res;
vector<pi> adj[maxN]; //original graph
vector<pi> adj2[maxN<<2]; //4-layered graph
int distS[maxN],distT[maxN];
void dijk(int dist[], int src){
    for(int i = 1; i <= N; ++i)dist[i] = INF;
    bool vis[maxN];
    memset(vis,false,sizeof(vis));
    priority_queue<pi,vector<pi>,cmp> Q;
    Q.push(pi(0,src));
    dist[src] = 0;
    while(!Q.empty()){
        pi p = Q.top(); Q.pop();
        int d = p.fi; int loc = p.se;
        if(vis[loc])continue;
        vis[loc] = true;
        for(auto x: adj[loc]){
            if(dist[loc] + x.se < dist[x.fi]){
                dist[x.fi] = dist[loc] + x.se;
                if(!vis[x.fi]){
                    Q.push(pi(dist[x.fi],x.fi));
                }
            }
        }
    }
}
//for dijkstra on the layered graph
int dist[maxN<<2];
bool vis[maxN<<2];
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    //freopen("../test.in","r",stdin);
    cin >> N >> M >> S >> T >> U >> V;
    for(int i = 1; i <= M; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        adj[a].pb(pi(b,c));
        adj[b].pb(pi(a,c));
        //layer 1 to layer 1
        adj2[a].pb(pi(b,c));
        adj2[b].pb(pi(a,c));
        //layer 1 to layer 2, enter into forward commuter pass (S->T)
        adj2[a].pb(pi(N+a,0));
        adj2[b].pb(pi(N+b,0));
        //layer 1 to layer 3, enter into backward commuter pass (T->S)
        adj2[a].pb(pi(2*N+a,0));
        adj2[b].pb(pi(2*N+b,0));
        //layer 1 to layer 4, for skipping commuter pass
        adj2[a].pb(pi(3*N+a,0));
        adj2[b].pb(pi(3*N+b,0));
        //layer 2 to layer 4, exiting commuter pass
        adj2[N+i].pb(pi(3*N+i,0));
        //layer 3 to layer 4, exiting commuter pass
        adj2[2*N+i].pb(pi(3*N+i,0));
        //layer 4 to layer 4
        adj2[3*N+a].pb(pi(3*N+b,c));
        adj2[3*N+b].pb(pi(3*N+a,c));
    }
    dijk(distS,S);
    dijk(distT,T);
    for(int i = 1; i <= N; ++i){
        for(auto x: adj[i]){
            if(distS[i] + x.se + distT[x.fi] == distS[T]){
                //Ensures edge x is a part of a shortest path from S to T
                //this edge must be from S->T and not T->S
                //layer 2 to layer 2
                adj2[N+i].pb(pi(N+x.fi,0));
                //layer 3 to layer 3
                adj2[2*N+x.fi].pb(pi(2*N+i,0));
            }
        }
    }
    //dijk for adj2, src = U
    for(int i = 1; i <= 4*N; ++i)dist[i] = INF;
    memset(vis,false,sizeof(vis));
    priority_queue<pi,vector<pi>,cmp> Q;
    Q.push(pi(0,U));
    dist[U] = 0;
    while(!Q.empty()){
        pi p = Q.top(); Q.pop();
        int loc = p.se;
        if(vis[loc])continue;
        vis[loc] = true;
        for(auto x: adj2[loc]){
            if(dist[loc] + x.se < dist[x.fi]){
                dist[x.fi] = dist[loc] + x.se;
                if(!vis[x.fi]){
                    Q.push(pi(dist[x.fi],x.fi));
                }
            }
        }
    }
    cout << dist[3*N+V] << '\n';
}

Compilation message

commuter_pass.cpp: In function 'void dijk(long long int*, long long int)':
commuter_pass.cpp:31:13: warning: unused variable 'd' [-Wunused-variable]
   31 |         int d = p.fi; int loc = p.se;
      |             ^

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 937 ms 101496 KB Output is correct
2 Correct 891 ms 99732 KB Output is correct
3 Correct 1010 ms 102260 KB Output is correct
4 Correct 949 ms 98348 KB Output is correct
5 Correct 1034 ms 101584 KB Output is correct
6 Correct 913 ms 101316 KB Output is correct
7 Correct 1012 ms 101552 KB Output is correct
8 Correct 1012 ms 101036 KB Output is correct
9 Correct 907 ms 98796 KB Output is correct
10 Correct 794 ms 98308 KB Output is correct
11 Correct 508 ms 63932 KB Output is correct
12 Correct 988 ms 99052 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 990 ms 99416 KB Output is correct
2 Correct 973 ms 99876 KB Output is correct
3 Correct 1006 ms 100600 KB Output is correct
4 Correct 1020 ms 99672 KB Output is correct
5 Correct 1061 ms 100016 KB Output is correct
6 Correct 1018 ms 100968 KB Output is correct
7 Correct 1075 ms 102452 KB Output is correct
8 Correct 1303 ms 99692 KB Output is correct
9 Correct 1014 ms 99964 KB Output is correct
10 Correct 1002 ms 99388 KB Output is correct
11 Correct 605 ms 64844 KB Output is correct
12 Correct 980 ms 101268 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 33424 KB Output is correct
2 Correct 15 ms 24960 KB Output is correct
3 Correct 16 ms 25012 KB Output is correct
4 Correct 54 ms 40832 KB Output is correct
5 Correct 35 ms 33348 KB Output is correct
6 Correct 20 ms 25308 KB Output is correct
7 Correct 18 ms 25632 KB Output is correct
8 Correct 20 ms 26000 KB Output is correct
9 Correct 20 ms 25236 KB Output is correct
10 Correct 36 ms 33432 KB Output is correct
11 Correct 16 ms 24920 KB Output is correct
12 Correct 14 ms 24908 KB Output is correct
13 Correct 14 ms 24908 KB Output is correct
14 Correct 15 ms 25044 KB Output is correct
15 Correct 18 ms 25036 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 937 ms 101496 KB Output is correct
2 Correct 891 ms 99732 KB Output is correct
3 Correct 1010 ms 102260 KB Output is correct
4 Correct 949 ms 98348 KB Output is correct
5 Correct 1034 ms 101584 KB Output is correct
6 Correct 913 ms 101316 KB Output is correct
7 Correct 1012 ms 101552 KB Output is correct
8 Correct 1012 ms 101036 KB Output is correct
9 Correct 907 ms 98796 KB Output is correct
10 Correct 794 ms 98308 KB Output is correct
11 Correct 508 ms 63932 KB Output is correct
12 Correct 988 ms 99052 KB Output is correct
13 Correct 990 ms 99416 KB Output is correct
14 Correct 973 ms 99876 KB Output is correct
15 Correct 1006 ms 100600 KB Output is correct
16 Correct 1020 ms 99672 KB Output is correct
17 Correct 1061 ms 100016 KB Output is correct
18 Correct 1018 ms 100968 KB Output is correct
19 Correct 1075 ms 102452 KB Output is correct
20 Correct 1303 ms 99692 KB Output is correct
21 Correct 1014 ms 99964 KB Output is correct
22 Correct 1002 ms 99388 KB Output is correct
23 Correct 605 ms 64844 KB Output is correct
24 Correct 980 ms 101268 KB Output is correct
25 Correct 42 ms 33424 KB Output is correct
26 Correct 15 ms 24960 KB Output is correct
27 Correct 16 ms 25012 KB Output is correct
28 Correct 54 ms 40832 KB Output is correct
29 Correct 35 ms 33348 KB Output is correct
30 Correct 20 ms 25308 KB Output is correct
31 Correct 18 ms 25632 KB Output is correct
32 Correct 20 ms 26000 KB Output is correct
33 Correct 20 ms 25236 KB Output is correct
34 Correct 36 ms 33432 KB Output is correct
35 Correct 16 ms 24920 KB Output is correct
36 Correct 14 ms 24908 KB Output is correct
37 Correct 14 ms 24908 KB Output is correct
38 Correct 15 ms 25044 KB Output is correct
39 Correct 18 ms 25036 KB Output is correct
40 Correct 962 ms 101840 KB Output is correct
41 Correct 1010 ms 102472 KB Output is correct
42 Correct 960 ms 103148 KB Output is correct
43 Correct 559 ms 68236 KB Output is correct
44 Correct 557 ms 68268 KB Output is correct
45 Correct 940 ms 111332 KB Output is correct
46 Correct 919 ms 112380 KB Output is correct
47 Correct 853 ms 103116 KB Output is correct
48 Correct 561 ms 67824 KB Output is correct
49 Correct 733 ms 101572 KB Output is correct
50 Correct 966 ms 110548 KB Output is correct
51 Correct 916 ms 112540 KB Output is correct