// author: gary
// created: 2018/09/03 13:29:03
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <limits>
#include <utility>
#include <functional>
#include <string>
#include <bitset>
#include <deque>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <algorithm>
#include <iostream>
#include <sstream>
using namespace std;
#define SZ(x) ( (int) (x).size() )
#define ALL(c) (c).begin(), (c).end()
#define CNT(c, x) ((c).find(x) != (c).end())
#define mp make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
template<class T> bool cmax(T& a, T b) { if(a < b) { a = b; return true; } return false; }
template<class T> bool cmin(T& a, T b) { if(a > b) { a = b; return true; } return false; }
const int INF = 1e9;
const int N = 100005;
int n, m, S, T, U, V;
vector<pii> E[N];
ll d[2][N]; // d[U][.] and d[V][.]
void dijkstra(ll* dist, int u) {
priority_queue<pli, vector<pli>, greater<pli>> pq;
fill(dist, dist + N, 1LL<<62);
dist[u] = 0;
pq.push(mp(0, u));
while(!pq.empty()) {
pli t = pq.top();
pq.pop();
if(dist[t.second] < t.first) {
continue;
}
for(auto& e: E[t.second]) {
if(cmin(dist[e.first], t.first + e.second)) {
pq.push(mp(dist[e.first], e.first));
}
}
}
}
ll dist[N];
ll min_d[2][N];
ll min_sum[N];
ll calc(int U, int V) {
priority_queue<pli, vector<pli>, greater<pli>> pq;
fill(dist, dist + N, 1LL<<62);
fill(min_sum, min_sum + N, 1LL<<62);
for(int i = 1; i <= n; i++) {
min_sum[i] = 1LL<<62;
min_d[0][i] = min_d[1][i] = 1LL<<62;
}
dist[U] = 0;
min_sum[U] = d[0][U] + d[1][U];
min_d[0][U] = d[0][U];
min_d[1][U] = d[1][U];
pq.push(mp(0LL, U));
while(!pq.empty()) {
pli t = pq.top();
pq.pop();
int u = t.second;
ll cost = t.first;
if(dist[u] < cost) {
continue;
}
for(auto& e: E[u]) {
int v = e.first;
ll ndist = cost + e.second;
if(dist[v] < ndist) {
continue;
}
if(dist[v] > ndist) {
for(int i = 0; i < 2; i++) {
min_d[i][v] = d[i][v];
}
min_sum[v] = 1LL << 62;
dist[v] = ndist;
pq.push(mp(dist[v], v));
}
for(int i = 0; i < 2; i++) {
cmin(min_d[i][v], min_d[i][u]);
}
cmin(min_sum[v], min_d[0][v] + d[1][v]);
cmin(min_sum[v], min_d[1][v] + d[0][v]);
cmin(min_sum[v], min_sum[u]);
}
}
/*
for(int i = 1; i <= n; i++) {
printf("min_sum: %d %lld\n", i, min_sum[i]);
}
*/
return min_sum[V];
}
int main() {
cin >> n >> m >> S >> T >> U >> V;
for(int i = 0; i < m; i++) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
E[u].emplace_back(v, w);
E[v].emplace_back(u, w);
}
dijkstra(d[0], U);
dijkstra(d[1], V);
// for(int i = 1; i <= n; i++) { printf("%lld %lld\n", d[0][i], d[1][i]); }
printf("%lld\n", min(d[0][V], calc(S, T)));
return 0;
}
Compilation message
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:128:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &u, &v, &w);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
341 ms |
16920 KB |
Output is correct |
2 |
Correct |
349 ms |
16920 KB |
Output is correct |
3 |
Correct |
388 ms |
16920 KB |
Output is correct |
4 |
Correct |
344 ms |
16920 KB |
Output is correct |
5 |
Correct |
401 ms |
16920 KB |
Output is correct |
6 |
Correct |
350 ms |
17104 KB |
Output is correct |
7 |
Correct |
365 ms |
17104 KB |
Output is correct |
8 |
Correct |
346 ms |
17104 KB |
Output is correct |
9 |
Correct |
328 ms |
17104 KB |
Output is correct |
10 |
Correct |
327 ms |
17104 KB |
Output is correct |
11 |
Correct |
129 ms |
17104 KB |
Output is correct |
12 |
Correct |
359 ms |
17104 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
382 ms |
17104 KB |
Output is correct |
2 |
Correct |
377 ms |
17104 KB |
Output is correct |
3 |
Correct |
380 ms |
17104 KB |
Output is correct |
4 |
Correct |
384 ms |
19392 KB |
Output is correct |
5 |
Correct |
388 ms |
22720 KB |
Output is correct |
6 |
Correct |
356 ms |
26300 KB |
Output is correct |
7 |
Correct |
379 ms |
30004 KB |
Output is correct |
8 |
Correct |
388 ms |
33548 KB |
Output is correct |
9 |
Correct |
393 ms |
37096 KB |
Output is correct |
10 |
Correct |
374 ms |
40356 KB |
Output is correct |
11 |
Correct |
140 ms |
40356 KB |
Output is correct |
12 |
Correct |
364 ms |
46088 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
46088 KB |
Output is correct |
2 |
Correct |
6 ms |
46088 KB |
Output is correct |
3 |
Correct |
7 ms |
46088 KB |
Output is correct |
4 |
Correct |
28 ms |
46088 KB |
Output is correct |
5 |
Correct |
16 ms |
46088 KB |
Output is correct |
6 |
Correct |
7 ms |
46088 KB |
Output is correct |
7 |
Correct |
7 ms |
46088 KB |
Output is correct |
8 |
Correct |
8 ms |
46088 KB |
Output is correct |
9 |
Correct |
8 ms |
46088 KB |
Output is correct |
10 |
Correct |
16 ms |
46088 KB |
Output is correct |
11 |
Correct |
6 ms |
46088 KB |
Output is correct |
12 |
Correct |
7 ms |
46088 KB |
Output is correct |
13 |
Correct |
7 ms |
46088 KB |
Output is correct |
14 |
Correct |
7 ms |
46088 KB |
Output is correct |
15 |
Correct |
7 ms |
46088 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
341 ms |
16920 KB |
Output is correct |
2 |
Correct |
349 ms |
16920 KB |
Output is correct |
3 |
Correct |
388 ms |
16920 KB |
Output is correct |
4 |
Correct |
344 ms |
16920 KB |
Output is correct |
5 |
Correct |
401 ms |
16920 KB |
Output is correct |
6 |
Correct |
350 ms |
17104 KB |
Output is correct |
7 |
Correct |
365 ms |
17104 KB |
Output is correct |
8 |
Correct |
346 ms |
17104 KB |
Output is correct |
9 |
Correct |
328 ms |
17104 KB |
Output is correct |
10 |
Correct |
327 ms |
17104 KB |
Output is correct |
11 |
Correct |
129 ms |
17104 KB |
Output is correct |
12 |
Correct |
359 ms |
17104 KB |
Output is correct |
13 |
Correct |
382 ms |
17104 KB |
Output is correct |
14 |
Correct |
377 ms |
17104 KB |
Output is correct |
15 |
Correct |
380 ms |
17104 KB |
Output is correct |
16 |
Correct |
384 ms |
19392 KB |
Output is correct |
17 |
Correct |
388 ms |
22720 KB |
Output is correct |
18 |
Correct |
356 ms |
26300 KB |
Output is correct |
19 |
Correct |
379 ms |
30004 KB |
Output is correct |
20 |
Correct |
388 ms |
33548 KB |
Output is correct |
21 |
Correct |
393 ms |
37096 KB |
Output is correct |
22 |
Correct |
374 ms |
40356 KB |
Output is correct |
23 |
Correct |
140 ms |
40356 KB |
Output is correct |
24 |
Correct |
364 ms |
46088 KB |
Output is correct |
25 |
Correct |
16 ms |
46088 KB |
Output is correct |
26 |
Correct |
6 ms |
46088 KB |
Output is correct |
27 |
Correct |
7 ms |
46088 KB |
Output is correct |
28 |
Correct |
28 ms |
46088 KB |
Output is correct |
29 |
Correct |
16 ms |
46088 KB |
Output is correct |
30 |
Correct |
7 ms |
46088 KB |
Output is correct |
31 |
Correct |
7 ms |
46088 KB |
Output is correct |
32 |
Correct |
8 ms |
46088 KB |
Output is correct |
33 |
Correct |
8 ms |
46088 KB |
Output is correct |
34 |
Correct |
16 ms |
46088 KB |
Output is correct |
35 |
Correct |
6 ms |
46088 KB |
Output is correct |
36 |
Correct |
7 ms |
46088 KB |
Output is correct |
37 |
Correct |
7 ms |
46088 KB |
Output is correct |
38 |
Correct |
7 ms |
46088 KB |
Output is correct |
39 |
Correct |
7 ms |
46088 KB |
Output is correct |
40 |
Correct |
370 ms |
53488 KB |
Output is correct |
41 |
Correct |
356 ms |
56444 KB |
Output is correct |
42 |
Correct |
344 ms |
60760 KB |
Output is correct |
43 |
Correct |
144 ms |
60760 KB |
Output is correct |
44 |
Correct |
132 ms |
60760 KB |
Output is correct |
45 |
Correct |
316 ms |
67988 KB |
Output is correct |
46 |
Correct |
345 ms |
71328 KB |
Output is correct |
47 |
Correct |
344 ms |
75248 KB |
Output is correct |
48 |
Correct |
151 ms |
75248 KB |
Output is correct |
49 |
Correct |
323 ms |
82128 KB |
Output is correct |
50 |
Correct |
319 ms |
84028 KB |
Output is correct |
51 |
Correct |
316 ms |
87376 KB |
Output is correct |