Submission #471933

#	Time	Username	Problem	Language	Result	Execution time	Memory
471933		keta_tsimakuridze	Commuter Pass (JOI18_commuter_pass)	C++14	0 / 100	553 ms	41384 KiB

commuter_pass

#include<bits/stdc++.h>
#define f first
#define s second
#define int long long
#define pii pair<int,int>
using namespace std;
const int N = 2e5 + 5, inf = 1e16;
int t, d[4][N], n, m, mn[N][2], in[N], fix[N];
vector<int> adj[2][N];
vector<pii> V[N];
void dijkstra(int u,int t) {
	for(int i = 1; i <= n; i++) d[t][i] = inf;
	d[t][u] = 0;
	priority_queue<pii,vector<pii>,greater<pii> > q;
	q.push({0,u});
	while(q.size()) {
		int u = q.top().s;
		int dist = q.top().f;
		q.pop();
		if(dist > d[t][u]) continue;
		for(int i = 0; i < V[u].size(); i++) {
			int v = V[u][i].f, c = V[u][i].s;
			if(d[t][v] > d[t][u] + c) {
				adj[t][v].clear();
				adj[t][v].push_back(u);
				d[t][v] = d[t][u] + c;
				q.push({d[t][v],v});
			}
			else if(d[t][v] == d[t][u] + c) adj[t][v].push_back(u);
		}
	}
}
void dfs(int u) {
	if(fix[u]) return;
	fix[u] = 1;
	for(int j = 0; j < adj[0][u].size(); j++) {
		in[adj[0][u][j]]++; 
		dfs(adj[0][u][j]);
	}
}
main(){
	cin >> n >> m;
	int s,t,u,v;
	cin >> s >> t >> u >> v;
	for(int i = 1; i <= m; i++) {
		int u,v,c;
		cin >> u >> v >> c;
		V[u].push_back({v,c});
		V[v].push_back({u,c});
	}
	dijkstra(u,1);
	dijkstra(v,2); 
	dijkstra(s,0);
	queue<int> q;
	q.push(t);
	dfs(t); // DAG
	int ans = d[1][v];
	for(int i = 1; i <= n; i++) {
		for(int t = 0; t < 2; t++) mn[i][t] = inf;
	}
	while(q.size()) {
		int u = q.front(); 
		q.pop();		
		mn[u][0] = min(mn[u][0],d[1][u]);
		mn[u][1] = min(mn[u][1], d[2][u]); 
		ans = min(ans, min(mn[u][0] + d[2][u], mn[u][1] + d[1][u]));

		for(int i = 0; i < adj[0][u].size(); i++) {
			in[adj[0][u][i]]--;
			for(int t = 0; t < 2; t++)
			mn[adj[0][u][i]][t] = min(mn[adj[0][u][i]][t], mn[u][t]);
			if(!in[adj[0][u][i]]) q.push(adj[0][u][i]);
		}
	}
	cout << ans;
 }

Compilation message (stderr)

commuter_pass.cpp: In function 'void dijkstra(long long int, long long int)':
commuter_pass.cpp:21:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |   for(int i = 0; i < V[u].size(); i++) {
      |                  ~~^~~~~~~~~~~~~
commuter_pass.cpp: In function 'void dfs(long long int)':
commuter_pass.cpp:36:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |  for(int j = 0; j < adj[0][u].size(); j++) {
      |                 ~~^~~~~~~~~~~~~~~~~~
commuter_pass.cpp: At global scope:
commuter_pass.cpp:41:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   41 | main(){
      | ^~~~
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:68:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |   for(int i = 0; i < adj[0][u].size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~~~~

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