제출 #91366

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
91366		aminra	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	1113 ms	153968 KiB

commuter_pass

//tavakol bar khoda
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int MAXN = (int)1e5 + 7;
const int MOD = (int)1e9 + 7;
const int infint = (int)1e8 + 3;
const ll inf = (ll)1e18;
ll n, m, distU[MAXN], distV[MAXN], distS[MAXN], S, T, U, V, visited[MAXN], dp[MAXN], way[MAXN];
vector<pair<ll, ll> > G[MAXN];
vector<int> dag[MAXN], topol;
void dijkstraU()
{
	for (int i = 1; i <= n; i++)
		distU[i] = inf;
	distU[U] = 0;
	set<pair<ll, ll> > S;
	for (int i = 1; i <= n; i++)
		S.insert({distU[i], i});
	while(S.size())
	{
		pair<ll, ll> P = *S.begin();
		S.erase(P);
		for (auto v : G[P.second])
			if(distU[v.first] > P.first + v.second)
			{
				S.erase({distU[v.first], v.first});
				distU[v.first] = P.first + v.second;
				S.insert({distU[v.first], v.first});
			}
	}
}

void dijkstraV()
{
	for (int i = 1; i <= n; i++)
		distV[i] = inf;
	distV[V] = 0;
	set<pair<ll, ll> > S;
	for (int i = 1; i <= n; i++)
		S.insert({distV[i], i});
	while(S.size())
	{
		pair<ll, ll> P = *S.begin();
		S.erase(P);
		for (auto v : G[P.second])
			if(distV[v.first] > P.first + v.second)
			{
				S.erase({distV[v.first], v.first});
				distV[v.first] = P.first + v.second;
				S.insert({distV[v.first], v.first});
			}
	}
}

void dijkstraS()
{
	for (int i = 1; i <= n; i++)
		distS[i] = inf;
	distS[S] = 0;
	set<pair<ll, ll> > S;
	for (int i = 1; i <= n; i++)
		S.insert({distS[i], i});
	while(S.size())
	{
		pair<ll, ll> P = *S.begin();
		S.erase(P);
		for (auto v : G[P.second])
			if(distS[v.first] > P.first + v.second)
			{
				S.erase({distS[v.first], v.first});
				distS[v.first] = P.first + v.second;
				S.insert({distS[v.first], v.first});
			}
	}
}

void dfs(int u)
{
	visited[u] = 1;
	for (auto v : dag[u])
		if(!visited[v])
			dfs(v);
	topol.push_back(u);
}
void DFS(int u)
{
	way[u] = 1;
	for (auto v : dag[u])
		if(!way[v])
			DFS(v);
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n >> m;
	cin >> S >> T >> U >> V;
	for (int i = 0; i < m; i++)
	{
		ll a, b, w;
		cin >> a >> b >> w;
		G[a].push_back({b, w});
		G[b].push_back({a, w});
	}
	dijkstraU();
	dijkstraV();
	dijkstraS();
	for (int i = 1; i <= n; i++)
		for (auto u : G[i])
			if(distS[i] + u.second == distS[u.first])
				dag[u.first].push_back(i);
	DFS(T);
	
	for (int i = 1; i <= n; i++)
		dag[i].clear();
	memset(visited, 0, sizeof visited);
	
	
	for (int i = 1; i <= n; i++)
		for (auto u : G[i])
			if(distS[i] + u.second == distS[u.first] && way[u.first])
				dag[i].push_back(u.first);
	for (int i = 1; i <= n; i++)
		if(!visited[i])
			dfs(i);
	reverse(topol.begin(), topol.end());
	ll ans = distU[V];
	for (int i = topol.size() - 1; i >= 0; i--)
	{
		int u = topol[i];
		dp[u] = distV[u];
		for (auto v : dag[u])
			dp[u] = min(dp[u], dp[v]);
		ans = min(ans, distU[u] + dp[u]);
	}

	for (int i = 1; i <= n; i++)
		dag[i].clear();
	topol.clear();
	memset(visited, 0, sizeof visited);
	for (int i = 1; i <= n; i++)
		for (auto u : G[i])
			if(distS[i] + u.second == distS[u.first] && way[u.first])
				dag[u.first].push_back(i);
	for (int i = 1; i <= n; i++)
		if(!visited[i])
			dfs(i);
	reverse(topol.begin(), topol.end());
	for (int i = topol.size() - 1; i >= 0; i--)
	{
		int u = topol[i];
		dp[u] = distV[u];
		for (auto v : dag[u])
			dp[u] = min(dp[u], dp[v]);
		ans = min(ans, distU[u] + dp[u]);
	}
	cout << ans;
}

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