oj.uz

Submission #82975

# Submission time Handle Problem Language Result Execution time Memory
82975 2018-11-03T11:27:45 Z Vasiljko Commuter Pass (JOI18_commuter_pass) C++14
100 / 100
 485 ms 81316 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll MOD = 1e9+7;
const int N =1e5+5;
const ll INF = 1e18;

int n,m,T;
bool vis[N];
ll du[N],dv[N],ds[N],dt[N],d1[N],d2[N],dp[N],ans;
vector<pair<int,ll> >v[2*N];
priority_queue<pair<ll,int> >pq;
multiset<ll>su,sv;

void Dijkstra(ll *d,int s){
    for(int i=1;i<=N;i++)d[i]=INF;
    d[s]=0;
    pq.push({-d[s],s});

    while(!pq.empty()){
        auto cur=pq.top();
        pq.pop();

        for(auto e:v[cur.second]){
            if(d[cur.second]+e.second<d[e.first]){
                d[e.first]=d[cur.second]+e.second;
                pq.push({-d[e.first],e.first});
            }
        }
    }
}

ll dfs(int s,int dir){
    if(vis[s])return dp[s];
    vis[s]=true;
    dp[s]=du[s];
    for(auto e:v[s]){
        if(dir==0){//go from s to t
            if(ds[s]+e.second+dt[e.first]==ds[T]){
                dp[s]=min(dp[s],dfs(e.first,dir));
            }
        }else{
            if(dt[s]+e.second+ds[e.first]==ds[T]){
                dp[s]=min(dp[s],dfs(e.first,dir));
            }
        }
    }
    ans=min(ans,dp[s]+dv[s]);
    return dp[s];
}

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int s,t,a,b,x,y,z;

    cin>>n>>m;
    cin>>s>>t;
    cin>>a>>b;

    T=t;

    for(int i=1;i<=m;i++){
        cin>>x>>y>>z;
        v[x].push_back({y,z});
        v[y].push_back({x,z});
    }

    Dijkstra(du,a);
    Dijkstra(dv,b);
    Dijkstra(ds,s);
    Dijkstra(dt,t);

    ans=du[b];

    memset(vis,false,sizeof(vis));
    dfs(s,0);
    memset(vis,0,sizeof(vis));
    dfs(t,1);

    cout<<ans;
    return 0;
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 407 ms 19940 KB Output is correct
2 Correct 433 ms 24384 KB Output is correct
3 Correct 423 ms 31032 KB Output is correct
4 Correct 389 ms 31112 KB Output is correct
5 Correct 400 ms 35260 KB Output is correct
6 Correct 387 ms 38592 KB Output is correct
7 Correct 471 ms 42692 KB Output is correct
8 Correct 444 ms 46032 KB Output is correct
9 Correct 415 ms 49448 KB Output is correct
10 Correct 338 ms 53740 KB Output is correct
11 Correct 183 ms 53740 KB Output is correct
12 Correct 458 ms 60300 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 447 ms 62512 KB Output is correct
2 Correct 462 ms 65340 KB Output is correct
3 Correct 483 ms 65340 KB Output is correct
4 Correct 485 ms 65340 KB Output is correct
5 Correct 451 ms 65488 KB Output is correct
6 Correct 430 ms 66624 KB Output is correct
7 Correct 443 ms 66760 KB Output is correct
8 Correct 416 ms 66760 KB Output is correct
9 Correct 366 ms 66760 KB Output is correct
10 Correct 395 ms 66760 KB Output is correct
11 Correct 142 ms 66760 KB Output is correct
12 Correct 399 ms 66840 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 66840 KB Output is correct
2 Correct 8 ms 66840 KB Output is correct
3 Correct 9 ms 66840 KB Output is correct
4 Correct 26 ms 66840 KB Output is correct
5 Correct 17 ms 66840 KB Output is correct
6 Correct 9 ms 66840 KB Output is correct
7 Correct 10 ms 66840 KB Output is correct
8 Correct 10 ms 66840 KB Output is correct
9 Correct 9 ms 66840 KB Output is correct
10 Correct 17 ms 66840 KB Output is correct
11 Correct 8 ms 66840 KB Output is correct
12 Correct 9 ms 66840 KB Output is correct
13 Correct 9 ms 66840 KB Output is correct
14 Correct 9 ms 66840 KB Output is correct
15 Correct 9 ms 66840 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 407 ms 19940 KB Output is correct
2 Correct 433 ms 24384 KB Output is correct
3 Correct 423 ms 31032 KB Output is correct
4 Correct 389 ms 31112 KB Output is correct
5 Correct 400 ms 35260 KB Output is correct
6 Correct 387 ms 38592 KB Output is correct
7 Correct 471 ms 42692 KB Output is correct
8 Correct 444 ms 46032 KB Output is correct
9 Correct 415 ms 49448 KB Output is correct
10 Correct 338 ms 53740 KB Output is correct
11 Correct 183 ms 53740 KB Output is correct
12 Correct 458 ms 60300 KB Output is correct
13 Correct 447 ms 62512 KB Output is correct
14 Correct 462 ms 65340 KB Output is correct
15 Correct 483 ms 65340 KB Output is correct
16 Correct 485 ms 65340 KB Output is correct
17 Correct 451 ms 65488 KB Output is correct
18 Correct 430 ms 66624 KB Output is correct
19 Correct 443 ms 66760 KB Output is correct
20 Correct 416 ms 66760 KB Output is correct
21 Correct 366 ms 66760 KB Output is correct
22 Correct 395 ms 66760 KB Output is correct
23 Correct 142 ms 66760 KB Output is correct
24 Correct 399 ms 66840 KB Output is correct
25 Correct 18 ms 66840 KB Output is correct
26 Correct 8 ms 66840 KB Output is correct
27 Correct 9 ms 66840 KB Output is correct
28 Correct 26 ms 66840 KB Output is correct
29 Correct 17 ms 66840 KB Output is correct
30 Correct 9 ms 66840 KB Output is correct
31 Correct 10 ms 66840 KB Output is correct
32 Correct 10 ms 66840 KB Output is correct
33 Correct 9 ms 66840 KB Output is correct
34 Correct 17 ms 66840 KB Output is correct
35 Correct 8 ms 66840 KB Output is correct
36 Correct 9 ms 66840 KB Output is correct
37 Correct 9 ms 66840 KB Output is correct
38 Correct 9 ms 66840 KB Output is correct
39 Correct 9 ms 66840 KB Output is correct
40 Correct 376 ms 66980 KB Output is correct
41 Correct 402 ms 71416 KB Output is correct
42 Correct 424 ms 75776 KB Output is correct
43 Correct 152 ms 75776 KB Output is correct
44 Correct 153 ms 76892 KB Output is correct
45 Correct 432 ms 81176 KB Output is correct
46 Correct 407 ms 81248 KB Output is correct
47 Correct 402 ms 81316 KB Output is correct
48 Correct 229 ms 81316 KB Output is correct
49 Correct 358 ms 81316 KB Output is correct
50 Correct 403 ms 81316 KB Output is correct
51 Correct 368 ms 81316 KB Output is correct