Submission #60560

#	Time	Username	Problem	Language	Result	Execution time	Memory
60560		gusfring	Commuter Pass (JOI18_commuter_pass)	C++14	16 / 100	791 ms	33460 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];

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]});
			}
		}
	}
}

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);
	ll mnu = 1000000000000000000LL, mnv = 1000000000000000000LL, ds = dists[T];
	for(int i=1; i<=N; ++i){
		if(min({dists[i], distt[i], distu[i], distv[i]}) == -1) continue;
		if(dists[i] + distt[i] == ds)	mnu = min(mnu, distu[i]), mnv = min(mnv, distv[i]);
	}
	printf("%lld\n", mnu + mnv);
	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:41: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:44: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: 0 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 45