oj.uz

답안 #42296

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
42296 2018-02-25T15:14:56 Z RezwanArefin01 Commuter Pass (JOI18_commuter_pass) C++14
15 / 100
 2000 ms 262144 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll, int> ii; 

const int maxn = 1e5 + 10;
vector<int> adj[maxn], cost[maxn];
vector<ll> du, dv, dt, ds, dp1, dp2;

void dijkstra(int s, int n, vector<ll> &d) {
	for(int i = 0; i < n; i++) d[i] = 1e18;
	priority_queue<ii, vector<ii>, greater<ii> > q;
	q.push({d[s] = 0, s});
	while(!q.empty()) {
		ii x = q.top(); q.pop(); 
		int u = x.second; ll c = x.first;
		for(int i = 0; i < adj[u].size(); i++) {
			int v = adj[u][i]; ll w = cost[u][i];
			if(d[v] > c + w) {
				d[v] = c + w;
				q.push({d[v], v});
			}
		}
	}
}

void compute(int s, int n, vector<ll> &dp, vector<ll> &d) {
	dp.resize(n + 1);
	d.resize(n + 1);
	for(int i = 1; i <= n; i++) {
		dp[i] = du[i]; 
		d[i] = 1e18;
	}
	priority_queue<ii, vector<ii>, greater<ii> > q; 
	q.push({d[s] = 0, s});

	while(!q.empty()) {
		ii x = q.top(); q.pop(); 
		int u = x.second; ll c = x.first;
		for(int i = 0; i < adj[u].size(); i++) {
			int v = adj[u][i]; ll w = cost[u][i];
			if(d[v] == c + w) {
			//	cout << u << " -> " << v << " ";
				d[v] = c + w; 
				dp[v] = min(dp[v], dp[u]);
				q.push({d[v], v});
			//	cout << dp[u] << " " << dp[v] << endl;
			} else if(d[v] > c + w) {
			//	cout << u << " -> " << v << " " ;
				d[v] = c + w;
				dp[v] = min(du[v], dp[u]);
				q.push({d[v], v});
			//	cout << dp[u] << " " << dp[v] << endl;
			}
		}
	}
}

int main(int argc, char const *argv[]) {
	int n, m, u, v, s, t; 
	scanf("%d %d", &n, &m); 
	scanf("%d %d", &s, &t);
	scanf("%d %d", &u, &v);
	for(int i = 0; i < m; i++) {
		int u, v, c;
		scanf("%d %d %d", &u, &v, &c);
		adj[u].push_back(v);
		adj[v].push_back(u);
		cost[u].push_back(c);
		cost[v].push_back(c);
	}	

	du.resize(n + 1);
	dv.resize(n + 1);
	ds.resize(n + 1);
	dt.resize(n + 1);
	dijkstra(u, n + 1, du);
	dijkstra(v, n + 1, dv);

	compute(s, n, dp1, ds); 
	compute(t, n, dp2, dt);

	ll Min = 1e18;

	for(int i = 1; i <= n; i++) {
		if(ds[t] == ds[i] + dt[i]) {
			Min = min(Min, dv[i] + min(dp1[i], dp2[i]));
		}
	}
	cout << min(Min, du[v]) << endl;

}

Compilation message

commuter_pass.cpp: In function 'void dijkstra(int, int, std::vector<long long int>&)':
commuter_pass.cpp:18:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < adj[u].size(); i++) {
                    ^
commuter_pass.cpp: In function 'void compute(int, int, std::vector<long long int>&, std::vector<long long int>&)':
commuter_pass.cpp:41:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < adj[u].size(); i++) {
                    ^
commuter_pass.cpp: In function 'int main(int, const char**)':
commuter_pass.cpp:62:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m); 
                        ^
commuter_pass.cpp:63:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &s, &t);
                        ^
commuter_pass.cpp:64:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &u, &v);
                        ^
commuter_pass.cpp:67:32: 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
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 553 ms 21376 KB Output is correct
2 Execution timed out 2048 ms 262144 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 689 ms 262144 KB Output is correct
2 Correct 697 ms 262144 KB Output is correct
3 Correct 674 ms 262144 KB Output is correct
4 Correct 727 ms 262144 KB Output is correct
5 Correct 682 ms 262144 KB Output is correct
6 Correct 641 ms 262144 KB Output is correct
7 Correct 712 ms 262144 KB Output is correct
8 Correct 662 ms 262144 KB Output is correct
9 Correct 636 ms 262144 KB Output is correct
10 Correct 631 ms 262144 KB Output is correct
11 Correct 239 ms 262144 KB Output is correct
12 Correct 553 ms 262144 KB Output is correct

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1048 ms 262144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 553 ms 21376 KB Output is correct
2 Execution timed out 2048 ms 262144 KB Time limit exceeded
3 Halted 0 ms 0 KB -