oj.uz

Submission #285373

# Submission time Handle Problem Language Result Execution time Memory
285373 2020-08-28T20:28:33 Z andrewwangva Commuter Pass (JOI18_commuter_pass) C++14
0 / 100
 384 ms 262148 KB 
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
using namespace std;

typedef long long ll;
vector<pair<ll, int>> edge[100001];
ll distu[100001]; ll distv[100001]; ll dists[100001];
bool visited[100001];
vector<pair<ll, ll>> pathc[100001];
ll MAX = 1000000000000000L; ll MOD = 1000000007L;
void djikstra(int s, ll dist[]){
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
    pair<ll, int> p; p.first = 0; p.second = s;
    pq.push(p);
    dist[s] = 0;
    while(!pq.empty()){
        pair<ll, int> cur = pq.top(); pq.pop();
        if(!visited[cur.second]){
            visited[cur.second] = true;
            for(pair<ll, int> e : edge[cur.second]){
                ll cost = e.first; int next = e.second;
                ll alt = cost + dist[cur.second];
                if(alt <= dist[next]){
                    dist[next] = alt;
                    e.first = dist[next];
                    pq.push(e);
                }
            }
        }
    }
}

void moddjikstra(int s, ll dist[]){
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
    pair<ll, int> p; p.first = 0; p.second = s;
    pair<ll, ll> fp; fp.first = distu[s]; fp.second = distv[s];
    pq.push(p);  pathc[s].push_back(fp);
    dist[s] = 0;
    while(!pq.empty()){
        pair<ll, int> cur = pq.top(); pq.pop();
        if(!visited[cur.second]){
            visited[cur.second] = true;
            for(pair<ll, int> e : edge[cur.second]){
                ll cost = e.first; int next = e.second;
                ll alt = cost + dist[cur.second];
                if(alt < dist[next]){
                    pathc[next].clear();
                }
                if(alt <= dist[next]){
                    for(pair<ll, ll> p : pathc[cur.second]){
                        if(distu[next] < p.first){
                            p.first = distu[next];
                        }
                        if(distv[next] < p.second){
                            p.second = distv[next];
                        }
                        pathc[next].push_back(p);
                    }
                    dist[next] = alt;
                    e.first = dist[next];
                    pq.push(e);
                }
            }
        }
    }
}
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n; int m; cin >> n >> m;
    int s; int t; int u; int v; cin>>s>>t>>u>>v;
    for(int i = 0; i < m; i++){
        int a,b,c; cin >> a >> b >> c;
        pair<ll, int> d; d.first = c; d.second = b;
        pair<ll, int> e; e.first = c; e.second = a;
        edge[a].push_back(d); edge[b].push_back(e);
    }
    for(int i = 0; i <= 100000; i++){
        dists[i] = MAX;
        distv[i] = MAX;
        distu[i] = MAX;
        visited[i] = false;
    }
    djikstra(u, distu);
    for(int i = 0; i <= 100000; i++)
        visited[i] = false;
    djikstra(v, distv);
    for(int i = 0; i <= 100000; i++)
        visited[i] = false;
    moddjikstra(1, dists);
    ll ans = distu[v];
    for(pair<ll, ll> p : pathc[t]){
        if(p.first + p.second < ans)
            ans = p.first + p.second;
    }
    cout << ans << endl;
    return 0;
}

Subtask #1
0 / 16.0

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

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 373 ms 25640 KB Output is correct
2 Incorrect 384 ms 24792 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 291 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

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