Submission #834474

#	Time	Username	Problem	Language	Result	Execution time	Memory
834474		vjudge1	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	335 ms	24820 KiB

commuter_pass

#include <bits/stdc++.h>
#define task "shipping"
#define fi first
#define se second
#define pii pair<int, int> 

using namespace std;
using ll = long long;

const ll mod = 1e9 + 19972207;  
const ll inf = 1e17;
const int arr = 200001;

ll dist[4][arr], dp[2][arr], ans = inf;
vector<pii> adj[arr];
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
int n, S = 0, T = 1, U = 2, V = 3, m;
int a[4];

void dijkstra(int u, int x){
    pq.emplace(0, u);
    dist[x][u] = 0;
    while(!pq.empty()){
        pair<ll, int> top = pq.top();
        pq.pop();
        int u = top.second;
        if(dist[x][u] != top.first)continue;
        for(auto [v, w] : adj[u]){
            if(dist[x][v] > dist[x][u] + w){
                dist[x][v] = dist[x][u] + w;
                pq.push({dist[x][v], v});
            }
        }
    }
}

void solve(int type) {
    vector<pair<ll, int>> res;

    for(int i = 1; i <= n; i++){
        if(dist[S][a[T]] == dist[S][i] + dist[T][i])
            res.push_back({dist[type][i], i});
    }
    sort(res.begin(), res.end());
    for(pair<ll, int> x : res){
        int u = x.second;
        dp[0][u] = dist[U][u];
        dp[1][u] = dist[V][u];
        for(auto [v, w] : adj[u]){
            if(dist[type][v] + w == dist[type][u]){
                dp[0][u] = min(dp[0][u], dp[0][v]);
                dp[1][u] = min(dp[1][u], dp[1][v]);
            }
        }
        ans = min(ans, min(dp[0][u] + dist[V][u], dp[1][u] + dist[U][u]));
    }
}

int main()
{
    ios_base::sync_with_stdio(false);   
    cin.tie(NULL); cout.tie(NULL);
	// freopen(task".inp" , "r" , stdin);
	// freopen(task".out" , "w" , stdout);
    cin >> n >> m;
    for(int i = 0; i < 4; i++)cin >> a[i];
    for(int i = 1; i <= m; i++){
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    memset(dist, 0x3f, sizeof dist);
    memset(dp, 0x3f, sizeof dp);
    for(int i = 0; i < 4; i++)
        dijkstra(a[i], i);
    ans = dist[V][a[U]];
    solve(0);
    solve(1);
    cout << ans << '\n';
}

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