Submission #934481

#	Time	Username	Problem	Language	Result	Execution time	Memory
934481		vjudge1	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	290 ms	26432 KiB

commuter_pass

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

#define N 100005
#define int long long
#define oo 1e18
#define se second
#define fi first

typedef pair<int, int> ii;


/*
	1 --> s
	2 --> t
	3 --> u
	4 --> v
*/

int n, d[5][N], m, s, t, u, v, dp[3][N];
vector<ii> adj[N];
vector<int> vex;

bool cmp (int& i, int& j){
	return d[1][i] < d[1][j];
}

void ditra(int s, int typ){
	for (int i = 1; i <= n; i++){
		d[typ][i] = oo;
	}
	priority_queue<ii, vector<ii>, greater<ii>> q;
	d[typ][s] = 0;
	q.push({0, s});
	while (!q.empty()){
		int du = q.top().fi;
		int u = q.top().se;
		q.pop();
		if (du != d[typ][u]) continue;
		for (auto x : adj[u]){
			int v = x.fi;
			int dv = x.se;
			if (d[typ][v] > dv + du){
				d[typ][v] = dv + du;
				q.push({d[typ][v], v});
			}
		}
	}
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
        
    cin >> n >> m;
    cin >> s >> t;
    cin >> u >> v;

    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});
    }

    ditra(s, 1);
    ditra(t, 2);
    ditra(u, 3);
    ditra(v, 4);

    for (int i = 1; i <= n; i++) {vex.push_back(i); dp[1][i] = d[3][i]; dp[2][i] = d[4][i];}
    sort(vex.begin(), vex.end(), cmp);
	int res = d[3][v];

	for (auto x : vex){
		for (auto xx : adj[x]){
			int v = xx.fi;
			int dv = xx.se;
			if (d[1][x] + dv + d[2][v] == d[1][t]){
				res = min(res, dp[1][x] + d[4][v]);
				res = min(res, dp[2][x] + d[3][v]);
				dp[1][v] = min(dp[1][v], dp[1][x]);
				dp[2][v] = min(dp[2][v], dp[2][x]);
			}
		}
	}

	cout << res;

    return 0;
}     

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