제출 #1067496

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1067496		shidou26	Commuter Pass (JOI18_commuter_pass)	C++14	31 / 100	154 ms	18836 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;

const long long inf = 0x3f3f3f3f3f3f3f3f;
const int N = (int) 1e5 + 7;
int n, m, s, t, x, y, u, v, w;
vector<pair<int, long long>> adj[N];
long long dist_s[N], dist_t[N], dist[N];
bool visited[N];

void dijkstra(int s, long long dist[]){
    memset(visited, false, sizeof visited);
    for(int i = 1; i <= n; i++){
        dist[i] = inf;
    }
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
    dist[s] = 0;
    pq.push({0, s});
    while(!pq.empty()){
        int u = pq.top().second;
        pq.pop();
        if(visited[u]) continue;
        visited[u] = true;
        for(int i = 0; i < (int) adj[u].size(); i++){
            int v = adj[u][i].first;
            long long w = adj[u][i].second;
            if(dist[v] > dist[u] + w){
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n >> m >> s >> t >> x >> y;
    for(int i = 1; i <= m; i++){
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    dijkstra(s, dist_s);
    dijkstra(t, dist_t);

    memset(dist, 0x3f, sizeof dist);
    memset(visited, false, sizeof visited);
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
    pq.push({0, x});
    dist[x] = 0;

    while(!pq.empty()){
        int u = pq.top().second;
        pq.pop();
        if(visited[u]) continue;
        visited[u] = true;
        for(int i = 0; i < (int) adj[u].size(); i++){
            int v = adj[u][i].first;
            long long w = adj[u][i].second;
            if(dist_s[u] + w + dist_t[v] == dist_s[t] || dist_s[v] + w + dist_t[u] == dist_s[t]){
                if(dist[v] > dist[u]){
                    dist[v] = dist[u];
                    pq.push({dist[v], v});
                }
            }
            else{
                if(dist[v] > dist[u] + w){
                    dist[v] = dist[u] + w;
                    pq.push({dist[v], v});
                }
            }
        }
    }

    cout << dist[y] << "\n";
}

• Subtask 1: 16 / 16
• Subtask 2: 15 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 45