oj.uz

답안 #948503

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
948503 2024-03-18T07:14:13 Z kornkin Commuter Pass (JOI18_commuter_pass) C++17
15 / 100
 2000 ms 37312 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long 

ll n, m, s, t, u, v, ans = 1e18, dis[100001];
vector<vector<pair<ll, ll>>> G(100001);
vector<int> E[100001], par[100001];
priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
bool vis[100001];

void reset() { for(int i = 1; i <= n; i++) dis[i] = LLONG_MAX; }

void cal(){
    reset();

    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;
                pq.push({dis[e], e});
            }
        }
    }

    ans = min(ans, dis[v]);
}

void solve(int d){
    if(d == s) cal();
    else {
        for(auto &e : par[d]){
            G[d].push_back({e, 0});
            G[e].push_back({d, 0});
            solve(e);
            G[d].pop_back();
            G[e].pop_back();
        }
    }   
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(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});

    }

    reset();

    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;
                pq.push({dis[e], e});
            }
        }
    }   

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

        if(vis[now]) continue;
        vis[now] = 1;
        for(auto &[e, w] : G[now]){
            if(dis[e] == dis[now] + w){
                par[e].push_back(now); 
                pq.push({dis[e], e});
            }
        }
    }  

    
    // for(int i = 1; i <= n; i++){
    //     cout << "i: " << i << '\n';
    //     for(auto &e : par[i]) cout << e << ' ';
    //     cout << '\n';
    // }
    
    solve(t);

    cout << ans;

    return 0;
}

Subtask #1
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 173 ms 22004 KB Output is correct
2 Execution timed out 2065 ms 23212 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 198 ms 27588 KB Output is correct
2 Correct 209 ms 28488 KB Output is correct
3 Correct 199 ms 27436 KB Output is correct
4 Correct 249 ms 28100 KB Output is correct
5 Correct 194 ms 29268 KB Output is correct
6 Correct 213 ms 32692 KB Output is correct
7 Correct 227 ms 37312 KB Output is correct
8 Correct 183 ms 28616 KB Output is correct
9 Correct 241 ms 29112 KB Output is correct
10 Correct 208 ms 27872 KB Output is correct
11 Correct 124 ms 26312 KB Output is correct
12 Correct 208 ms 33480 KB Output is correct

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2048 ms 9052 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 173 ms 22004 KB Output is correct
2 Execution timed out 2065 ms 23212 KB Time limit exceeded
3 Halted 0 ms 0 KB -