Submission #1156798

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156798		AgentPengin	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	283 ms	29344 KiB

commuter_pass

/**
 *    author:  AgentPengin ( Độc cô cầu bại )
 *    created: 23.12.2022 10:08:02
 *    too lazy to update time
**/
#include<bits/stdc++.h>

#define EL '\n'
#define fi first
#define se second
#define NAME "TASK"
#define ll long long
#define lcm(a,b) (a/gcd(a,b))*b
#define db(val) "["#val" = " << (val) << "] "
#define bend(v) (v).begin(),(v).end()
#define sz(v) (int)(v).size()
#define ex exit(0)
#define int ll

using namespace std;

const ll mod = 1e9 + 7;
const int inf = 1e18;
const int MAXN = 1e5 + 5;

int n, m, S, T, U, V, dp[MAXN], ans;
bool visited[MAXN], r[MAXN];
vector<pair<int,int>> adj[MAXN];
vector<int> dag[MAXN];

int dist[3][MAXN];


void dijkstra(int startNode, int index) {
	priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
	memset(dist[index], 0x3f, sizeof dist[index]);
	dist[index][startNode] = 0;
	pq.push(make_pair(dist[index][startNode], startNode));
	while(!pq.empty()) {
		int u = pq.top().se;
		int du = pq.top().fi;
		pq.pop();
		if (du != dist[index][u]) continue;
		for (auto it : adj[u]) {
			int v = it.fi;
			int uv = it.se;
			if (dist[index][v] > du + uv) {
				dist[index][v] = du + uv;
				pq.push(make_pair(dist[index][v], v));
			}
		}
	}
}

void dfs(int u) {
	visited[u] = true;
	for (auto v : dag[u]) {
		if (!visited[v]) {
			dfs(v);
		}
		dp[u] = min(dp[u], dp[v]);
		r[u] |= r[v];
	}
	if (r[u]) dp[u] = min(dp[u], dist[1][u]);
}

signed main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    if (ifstream(NAME".inp")) {
        freopen(NAME".inp","r",stdin);
        freopen(NAME".out","w",stdout);
    }
    cin >> n >> m >> S >> T >> U >> V;
    for (int i = 1, u, v, w;i <= m;i++) {
    	cin >> u >> v >> w;
    	adj[u].push_back(make_pair(v, w));
    	adj[v].push_back(make_pair(u, w));
    }
    dijkstra(U, 0); dijkstra(V, 1); dijkstra(S, 2);
    ans = dist[0][V];
    for (int i = 1;i <= n;i++) {
    	for (auto it : adj[i]) {
    		int v = it.fi;
    		int w = it.se;
    		if (dist[2][v] == dist[2][i] + w) {
    			dag[i].push_back(v);
    		}
    	}
    }
    memset(dp, 0x3f, sizeof dp);
    r[T] = 1;
    dfs(S);
    for (int i = 1;i <= n;i++) {
    	ans = min(ans, dist[0][i] + dp[i]);
    }
    dijkstra(T, 2);
    for (int i = 1;i <= n;i++) {
    	dag[i].clear();
    	for (auto it : adj[i]) {
    		int v = it.fi;
    		int w = it.se;
    		if (dist[2][v] == dist[2][i] + w) {
    			dag[i].push_back(v);
    		}
    	}
    }
    // for (auto x : dag[2]) cout << x << '\n';
    
    memset(dp, 0x3f, sizeof dp);
    memset(visited, 0, sizeof visited);
    memset(r, 0, sizeof r);
    r[S] = 1;
    dfs(T);
    for (int i = 1;i <= n;i++) {
    	ans = min(ans, dist[0][i] + dp[i]);
    }
    cout << ans;
    
    cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
    return 0;
}
// agent pengin wants to take apio (with anya-san)

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:70:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |         freopen(NAME".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:71:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |         freopen(NAME".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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