oj.uz

Submission #375721

# Submission time Handle Problem Language Result Execution time Memory
375721 2021-03-09T20:58:34 Z iliccmarko Commuter Pass (JOI18_commuter_pass) C++14
100 / 100
 446 ms 27084 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\n"
#define INF 1000000000
#define LINF 1000000000000000LL
#define pb push_back
#define all(x) x.begin(), x.end()
#define len(s) (int)s.size()
#define test_case { int t; cin>>t; while(t--)solve(); }
#define single_case solve();
#define line cerr<<"----------"<<endl;
#define ios { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cerr.tie(NULL); }
#define mod 1000000007LL
int n, m, s, t, u, v;
const int N = 1e5 + 50;
vector<pair<int, ll> > g[N];
vector<int> dag[N];
ll dpu[N], dpv[N];
ll diss[N], disv[N], dist[N], disu[N];
int vidjen[N];

void dijkstra(int src, ll dis[])
{
    for(int i = 0;i<N;i++) dis[i] = LINF, vidjen[i] = 0;
    dis[src] = 0;
    priority_queue<pair<ll, ll>, vector<pair<ll, ll> >, greater<pair<ll, ll> > > pq;
    pq.push(make_pair(0, src));
    while(len(pq))
    {
        int u = pq.top().second;
        pq.pop();
        if(vidjen[u]) continue;
        vidjen[u] = 1;
        for(auto x : g[u])
        {
            if(dis[x.first]>dis[u]+x.second)
            {
                dis[x.first] = dis[u] + x.second;
                pq.push(make_pair(dis[x.first], x.first));
            }
        }
    }
}

ll dfs(int u, ll d[], ll dp[])
{
    dp[u] = d[u];
    vidjen[u] = 1;
    for(auto x : dag[u])
    {
        if(vidjen[x])
        {
            dp[u] = min(dp[u], dp[x]);
            continue;
        }
        dp[u] = min(dp[u], dfs(x, d, dp));
    }
    return dp[u];
}

int main()
{
    ios
    for(int i = 0;i<N;i++) dpu[i] = dpv[i] = LINF;
    cin>>n>>m>>s>>t>>u>>v;
    for(int i = 0;i<m;i++)
    {
        int a, b, c;
        cin>>a>>b>>c;
        g[a].pb(make_pair(b, c));
        g[b].pb(make_pair(a, c));
    }
    dijkstra(s, diss);
    dijkstra(t, dist);
    dijkstra(u, disu);
    dijkstra(v, disv);
    ll res = disu[v];
    for(int i = 1;i<=n;i++)
    {
        for(auto x : g[i])
        {
            if(diss[i]+x.second+dist[x.first]==diss[t])
            {
                dag[i].pb(x.first);
            }
        }
    }
    for(int i = 1;i<=n;i++) vidjen[i] = 0;
    dfs(s, disu, dpu);
    for(int i = 1;i<=n;i++)
    {
        res = min(res, dpu[i]+disv[i]);
    }
    for(int i = 1;i<=n;i++) vidjen[i] = 0;
    dfs(s, disv, dpv);
    for(int i = 1;i<=n;i++)
    {
        res = min(res, dpv[i]+disu[i]);
    }

    cout<<res;

    return 0;
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 352 ms 23624 KB Output is correct
2 Correct 350 ms 22416 KB Output is correct
3 Correct 400 ms 27084 KB Output is correct
4 Correct 340 ms 24352 KB Output is correct
5 Correct 385 ms 22972 KB Output is correct
6 Correct 356 ms 24376 KB Output is correct
7 Correct 377 ms 23104 KB Output is correct
8 Correct 382 ms 23008 KB Output is correct
9 Correct 342 ms 23180 KB Output is correct
10 Correct 286 ms 22864 KB Output is correct
11 Correct 149 ms 19692 KB Output is correct
12 Correct 378 ms 23088 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 387 ms 22484 KB Output is correct
2 Correct 394 ms 22896 KB Output is correct
3 Correct 380 ms 22492 KB Output is correct
4 Correct 386 ms 22708 KB Output is correct
5 Correct 376 ms 23296 KB Output is correct
6 Correct 400 ms 25544 KB Output is correct
7 Correct 392 ms 26116 KB Output is correct
8 Correct 406 ms 22944 KB Output is correct
9 Correct 378 ms 23284 KB Output is correct
10 Correct 382 ms 22556 KB Output is correct
11 Correct 187 ms 20972 KB Output is correct
12 Correct 375 ms 25852 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 11500 KB Output is correct
2 Correct 7 ms 10220 KB Output is correct
3 Correct 8 ms 10220 KB Output is correct
4 Correct 23 ms 13548 KB Output is correct
5 Correct 15 ms 11884 KB Output is correct
6 Correct 7 ms 10220 KB Output is correct
7 Correct 8 ms 10348 KB Output is correct
8 Correct 8 ms 10348 KB Output is correct
9 Correct 7 ms 10220 KB Output is correct
10 Correct 15 ms 11884 KB Output is correct
11 Correct 7 ms 10092 KB Output is correct
12 Correct 7 ms 10092 KB Output is correct
13 Correct 7 ms 10220 KB Output is correct
14 Correct 7 ms 10220 KB Output is correct
15 Correct 7 ms 10220 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 352 ms 23624 KB Output is correct
2 Correct 350 ms 22416 KB Output is correct
3 Correct 400 ms 27084 KB Output is correct
4 Correct 340 ms 24352 KB Output is correct
5 Correct 385 ms 22972 KB Output is correct
6 Correct 356 ms 24376 KB Output is correct
7 Correct 377 ms 23104 KB Output is correct
8 Correct 382 ms 23008 KB Output is correct
9 Correct 342 ms 23180 KB Output is correct
10 Correct 286 ms 22864 KB Output is correct
11 Correct 149 ms 19692 KB Output is correct
12 Correct 378 ms 23088 KB Output is correct
13 Correct 387 ms 22484 KB Output is correct
14 Correct 394 ms 22896 KB Output is correct
15 Correct 380 ms 22492 KB Output is correct
16 Correct 386 ms 22708 KB Output is correct
17 Correct 376 ms 23296 KB Output is correct
18 Correct 400 ms 25544 KB Output is correct
19 Correct 392 ms 26116 KB Output is correct
20 Correct 406 ms 22944 KB Output is correct
21 Correct 378 ms 23284 KB Output is correct
22 Correct 382 ms 22556 KB Output is correct
23 Correct 187 ms 20972 KB Output is correct
24 Correct 375 ms 25852 KB Output is correct
25 Correct 15 ms 11500 KB Output is correct
26 Correct 7 ms 10220 KB Output is correct
27 Correct 8 ms 10220 KB Output is correct
28 Correct 23 ms 13548 KB Output is correct
29 Correct 15 ms 11884 KB Output is correct
30 Correct 7 ms 10220 KB Output is correct
31 Correct 8 ms 10348 KB Output is correct
32 Correct 8 ms 10348 KB Output is correct
33 Correct 7 ms 10220 KB Output is correct
34 Correct 15 ms 11884 KB Output is correct
35 Correct 7 ms 10092 KB Output is correct
36 Correct 7 ms 10092 KB Output is correct
37 Correct 7 ms 10220 KB Output is correct
38 Correct 7 ms 10220 KB Output is correct
39 Correct 7 ms 10220 KB Output is correct
40 Correct 350 ms 24060 KB Output is correct
41 Correct 344 ms 23196 KB Output is correct
42 Correct 353 ms 23016 KB Output is correct
43 Correct 205 ms 21996 KB Output is correct
44 Correct 193 ms 21996 KB Output is correct
45 Correct 382 ms 23720 KB Output is correct
46 Correct 446 ms 23764 KB Output is correct
47 Correct 352 ms 24460 KB Output is correct
48 Correct 206 ms 19948 KB Output is correct
49 Correct 305 ms 23932 KB Output is correct
50 Correct 387 ms 23028 KB Output is correct
51 Correct 391 ms 23980 KB Output is correct