Submission #1130765

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130765		ChuanChen	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	704 ms	40044 KiB

commuter_pass

/*
grafo direcionado dos caminho minimo de S->T é uma dag
S: ing = 0
T : outg = 0

dp no DAG
dpU(i) = custo de U até i
dpV(i) = custo de i até V

repita pro DAG de T->S
*/
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int lim = 1e5+5;
const ll inf = 1e18;

int n, m, S, T, U, V;
ll ans = inf;

//ARESTAS
struct Edge{
	int a, b, c;
	bool in_path;
};
vector<Edge> edges;
vector<int> adj[lim], weight[lim];
void addEdge(int a, int b, int c){
	edges.push_back({a, b, c, false});
	adj[a].push_back(b);
	adj[b].push_back(a);
	weight[a].push_back(c);
	weight[b].push_back(c);
}

//DIJK FOR MIN_PATHS
ll d[4][lim];
//d[0]: S->all, d[1]: T->all, d[2]: U->all, d[3]: V->all
void dijk(int r){
	set<pair<ll, int>> can;
	for(int i = 1; i <= n; i++) d[r][i] = inf;
	if(r == 0) d[r][S] = 0;
	else if(r == 1) d[r][T] = 0;
	else if(r == 2) d[r][U] = 0;
	else if(r == 3) d[r][V] = 0;

	for(int i = 1; i <= n; i++) can.emplace(d[r][i], i);

	while(!can.empty()){
		int no = can.begin()->second;
		can.erase(can.begin());
		for(int i = 0; i < adj[no].size(); i++){
			int v = adj[no][i], p = weight[no][i];
			if(d[r][v] > d[r][no] + p){
				can.erase({d[r][v], v});
				d[r][v] = d[r][no] + p;
				can.emplace(d[r][v], v);
			}
		}
	}
}
//DAGs
vector<int> dag[2][lim]; //dag[0] for S, dag[1] for T
ll dpU[2][lim], dpV[2][lim]; // 0 for S, 1 for T
// dpU(i) = custo de U até i
// dpV(i) = custo de i até V
int ing[2][lim];

void solve(int r){
	queue<int> can;

	for(int i = 1; i <= n; i++){
		if(ing[r][i] == 0) can.push(i);
	}

	while(!can.empty()){
		int no = can.front();
		can.pop();
		dpU[r][no] = min(dpU[r][no], d[2][no]);
		dpV[r][no] = min(dpV[r][no], d[3][no]);

		if(dag[r][no].empty()) continue;
		for(int v : dag[r][no]){
			ing[r][v]--;
			if(ing[r][v] == 0) can.push(v);

			if(r == 0){
				dpU[0][v] = min(dpU[0][v], dpU[0][no]);
				dpV[1][v] = min(dpV[1][v], dpV[1][no]);
			}
			else{
				dpU[1][v] = min(dpU[1][v], dpU[1][no]);
				dpV[0][v] = min(dpV[0][v], dpV[0][no]);
			}
		}
	}
}



int main(){
	cin.tie(0)->sync_with_stdio(0);
	if(fopen("in", "r")){
		freopen("in", "r", stdin);
		freopen("out", "w", stdout);
		freopen("err", "w", stderr);
	}
	cin >> n >> m;
	cin >> S >> T >> U >> V;

	for(int i = 1; i <= m; i++){
		int a, b, c; cin >> a >> b >> c;
		addEdge(a, b, c);
	}

	dijk(0);
	dijk(1);

	for(Edge &e : edges){
		if(d[0][e.a] + e.c + d[1][e.b] == d[0][T]){
			dag[0][e.a].push_back(e.b); ing[0][e.b]++;
			dag[1][e.b].push_back(e.a); ing[1][e.a]++;
		}
		if(d[0][e.b] + e.c + d[1][e.a] == d[0][T]){
			dag[1][e.a].push_back(e.b); ing[1][e.b]++;
			dag[0][e.b].push_back(e.a); ing[0][e.a]++;
		}
	}

	dijk(2);
	dijk(3);

	for(int i = 1; i <= n; i++)
		dpU[0][i] = dpV[0][i] = dpU[1][i] = dpV[1][i] = inf;
	solve(0);
	solve(1);

	ans = d[2][V];
	// cout << d[2][V] << '\n';
	for(int i = 1; i <= n; i++){
		// cerr << "Para i = " << i << '\n';
		// cerr << "Caminho S->T: " << dpU[0][i] << " + " << dpV[0][i] << '\n';
		// cerr << "Caminho T->S: " << dpU[1][i] << " + " << dpV[1][i] << '\n';
		ans = min({ans, dpU[0][i]+dpV[0][i], dpU[1][i]+dpV[1][i]});
	}
	cout << ans << '\n';
}

/*
0 -> antes de entrar CP
1 -> dentro do CP na direçao S->T
2 -> dentro do CP na direçao T->S
3 -> depois de sair CP

v - w com custo c
(v, 0) -> (w, 0) custo c
(v, 0) -> (w, 1) custo c se in_path(w)
(v, 0) -> (w, 2) custo c se in_path(w)

(v, 1) -> (w, 1) com custo 0 se can_go(S, v, w)
(v, 1) -> (w, 3) com custo c se in_path(v)

(v, 2) -> (w, 2) com custo 0 se can_go(T, v, w)
(v, 2) -> (w, 3) com custo 0 se in_path(v)

(v, 3) -> (w, 3) com custo c
*/

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:106:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |                 freopen("in", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~
commuter_pass.cpp:107:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |                 freopen("out", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:108:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |                 freopen("err", "w", stderr);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~

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