oj.uz

답안 #948475

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
948475 2024-03-18T06:50:50 Z kornkin Commuter Pass (JOI18_commuter_pass) C++17
15 / 100
 2000 ms 47212 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(vector<vector<pair<ll, ll>>> g){
    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(G);
    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 >> 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 210 ms 32456 KB Output is correct
2 Execution timed out 2065 ms 33272 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 222 ms 38084 KB Output is correct
2 Correct 201 ms 38856 KB Output is correct
3 Correct 207 ms 37692 KB Output is correct
4 Correct 223 ms 38420 KB Output is correct
5 Correct 248 ms 39740 KB Output is correct
6 Correct 216 ms 43464 KB Output is correct
7 Correct 244 ms 47212 KB Output is correct
8 Correct 257 ms 38732 KB Output is correct
9 Correct 237 ms 39680 KB Output is correct
10 Correct 203 ms 37852 KB Output is correct
11 Correct 136 ms 34740 KB Output is correct
12 Correct 295 ms 44236 KB Output is correct

Subtask #3
0 / 24.0

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

Subtask #4
0 / 45.0

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