Submission #60665

#	Time	Username	Problem	Language	Result	Execution time	Memory
60665		gusfring	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	799 ms	60040 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5 + 5;
typedef long long ll;

struct node{
	int u;
	ll w;
	bool operator<(const node &rhs) const{
		return w > rhs.w;
	}
};

vector<node> adj[MAXN];
int N, M, S, U, T, V;
ll dists[MAXN], distt[MAXN], distu[MAXN], distv[MAXN], dp[MAXN], res;

void dijkstra(int cur, ll *dist){
	for(int i=1; i<=N; ++i) dist[i] = -1;
	dist[cur] = 0;
	priority_queue<node> Q;
	Q.push((node){cur, 0});
	while(!Q.empty()){
		node it = Q.top(); Q.pop();
		int u = it.u;
		ll w = it.w;
		for(node it2 : adj[u]){
			int v = it2.u;
			ll ww = it2.w;
			if(dist[v] == -1 || dist[u] + ww < dist[v]){
				dist[v] = dist[u] + ww;
				Q.push((node){v, dist[v]});
			}
		}
	}
}

ll solve(int u, bool f){
	if(dp[u] == -1){
		if(dists[u] + distt[u] == distt[S]){
			dp[u] = distv[u];
			for(node it : adj[u])
				if((f && dists[u] + it.w == dists[it.u]) || (!f && distt[u] + it.w == distt[it.u]))
					dp[u] = min(solve(it.u, f), dp[u]);
			res = min(res, dp[u] + distu[u]);
		}
		else dp[u] = 1000000000000000000LL;
	}
	return dp[u];
}

int main(){
	scanf("%d %d %d %d %d %d", &N, &M, &S, &T, &U, &V);
	while(M--){
		int u, v, c;
		scanf("%d %d %d", &u, &v, &c);
		adj[u].push_back((node){v, c});
		adj[v].push_back((node){u, c});
	}
	dijkstra(S, dists);
	dijkstra(T, distt);
	dijkstra(U, distu);
	dijkstra(V, distv);
	res = distu[V];
	memset(dp, -1, sizeof(dp));
	solve(T, 0);
	memset(dp, -1, sizeof(dp));
	solve(S, 1);
	printf("%lld\n", res);
	return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void dijkstra(int, ll*)':
commuter_pass.cpp:28:6: warning: unused variable 'w' [-Wunused-variable]
   ll w = it.w;
      ^
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:55:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d %d %d %d", &N, &M, &S, &T, &U, &V);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:58:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &u, &v, &c);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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