oj.uz

Submission #948492

# Submission time Handle Problem Language Result Execution time Memory
948492 2024-03-18T07:02:18 Z kornkin Commuter Pass (JOI18_commuter_pass) C++17
0 / 100
 247 ms 20168 KB 
#include<bits/stdc++.h>
using namespace std;
#define pqpiig priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>>
#define ll long long 

ll n, m, s, t, u, v, dis[100001], par[100001];
vector<pair<ll, ll>> g[100001];

int main(){
    ios_base::sync_with_stdio(0);

    cin >> n >> m >> s >> t >> u >> v;
    for(ll i = 0; i < m; i++){
        ll u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});

        par[i] = i;
    }

    memset(dis, 0x3f3f3f3f, sizeof(dis));

    pqpiig pq;
    pq.push({0, s});
    dis[s] = 0;
    while(!pq.empty()){
        ll now = pq.top().second;
        pq.pop();


        for(auto &[e, w] : g[now]){
            if(dis[e] > dis[now] + w){
                dis[e] = dis[now] + w;
                par[e] = now; 
                pq.push({dis[e], e});
            }
        }
    }

    for(ll i = par[t]; par[i] != i; i = par[i]) g[i].push_back({par[i], 0}), g[par[i]].push_back({i, 0});

    memset(dis, 0x3f3f3f3f, sizeof(dis));
    
    pq.push({0, u});
    dis[u] = 0;
    while(!pq.empty()){
        ll now = pq.top().second;
        pq.pop();


        for(auto &[e, w] : g[now]){
            if(dis[e] > dis[now] + w){
                dis[e] = dis[now] + w;
                par[e] = now; 
                pq.push({dis[e], e});
            }
        }
    }

    //for(ll i = 1; i <= n; i++) cout << i << ": " << dis[i] << '\n'; 

    cout << dis[v];

    return 0;
}

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 16840 KB Output is correct
2 Correct 138 ms 15844 KB Output is correct
3 Correct 172 ms 20168 KB Output is correct
4 Incorrect 158 ms 15860 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 18368 KB Output is correct
2 Incorrect 247 ms 18632 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 4956 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 16840 KB Output is correct
2 Correct 138 ms 15844 KB Output is correct
3 Correct 172 ms 20168 KB Output is correct
4 Incorrect 158 ms 15860 KB Output isn't correct
5 Halted 0 ms 0 KB -