oj.uz

답안 #956489

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
956489 2024-04-02T05:30:48 Z pragmatist Commuter Pass (JOI18_commuter_pass) C++17
24 / 100
 127 ms 23172 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = (int)1e5+20;
const int inf = (int)1e9+7;
const long long INF = (long long)1e18+7;
const int MOD = 42043;

int sum(int x, int y) {
	x += y;
	if(x >= MOD) {
		x -= MOD;
	}
	return x;
}

int mult(int x, int y) {
	return 1ll*x*y%MOD;
}

int n, m, s1, t1, s2, t2;
vector<pair<int, int> > g[N];
long long d[305][305];

void dijkstra(int tp, int s) {
	fill(d[tp],  d[tp]+1+n, INF);
	d[tp][s] = 0;
	priority_queue<pair<long long, int> > q;
	q.push({0, s});
	while(!q.empty()) {
		long long cur_d = -q.top().first;
		int v = q.top().second;
		q.pop();
		for(auto [to, w] : g[v]) {
			if(d[tp][v]+w < d[tp][to]) {
				d[tp][to] = d[tp][v]+w;
				q.push({-d[tp][to], to});
			}
		}
	}	
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
	cin >> n >> m >> s1 >> t1 >> s2 >> t2;
	for(int i = 1; i <= m; ++i) {
		int u, v, w;
		cin >> u >> v >> w;
		g[u].push_back({v, w});
		g[v].push_back({u, w});
	}
	for(int i = 1; i <= n; ++i) {
		dijkstra(i, i);
	}           
	long long ans = d[s2][t2];
	for(int i = 1; i <= n; ++i) {
		for(int j = 1; j <= n; ++j) {
			if(d[s1][i]+d[i][j]+d[j][t1]==d[s1][t1]) {
				ans = min(ans, d[s2][i]+d[j][t2]);
				ans = min(ans, d[s2][j]+d[i][t2]);
			}
		}
	}
	cout << ans << "\n";
	return 0;
}

Compilation message

commuter_pass.cpp: In function 'void dijkstra(int, int)':
commuter_pass.cpp:32:13: warning: unused variable 'cur_d' [-Wunused-variable]
   32 |   long long cur_d = -q.top().first;
      |             ^~~~~

Subtask #1
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 127 ms 23124 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 123 ms 23172 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 4444 KB Output is correct
2 Correct 13 ms 3572 KB Output is correct
3 Correct 13 ms 3568 KB Output is correct
4 Correct 40 ms 5672 KB Output is correct
5 Correct 36 ms 4444 KB Output is correct
6 Correct 17 ms 3416 KB Output is correct
7 Correct 20 ms 3668 KB Output is correct
8 Correct 35 ms 3676 KB Output is correct
9 Correct 19 ms 3628 KB Output is correct
10 Correct 41 ms 4556 KB Output is correct
11 Correct 3 ms 3420 KB Output is correct
12 Correct 7 ms 3416 KB Output is correct
13 Correct 12 ms 3572 KB Output is correct
14 Correct 15 ms 3420 KB Output is correct
15 Correct 15 ms 3420 KB Output is correct

Subtask #4
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 127 ms 23124 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -