답안 #52300 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
52300	2018-06-25T08:35:22 Z	evpipis	Commuter Pass (JOI18_commuter_pass)	C++14	31 / 100	1024 ms	24024 KB

commuter_pass

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int, int> ii;

const int len = 1e5+5;
const ll inf = 1e16;
int n, m, s1, t1, s2, t2, best[len];
ll dis[5][len];
vector<ii> adj[len];
priority_queue<pair<ll, ii>, vector<pair<ll, ii> >, greater<pair<ll, ii> > > pq;

void dfs(int u){
    //printf("best %d\n", u);
    best[u] = 1;
    for (int j = 0; j < adj[u].size(); j++){
        ii v = adj[u][j];
        if (!best[v.fi] && dis[4][v.fi]+v.se == dis[4][u])
            dfs(v.fi);
    }
}

void path(int s, int hey){
    if (!hey){
        for (int j = 1; j <= n; j++)
            dis[4][j] = inf;
    }
    else{
        for (int i = 0; i < 4; i++)
            for (int j = 1; j <= n; j++)
                dis[i][j] = inf;
    }

    if (!hey){
        pq.push(mp(0, mp(4, s)));
    }
    else{
        if (best[s])
            pq.push(mp(0, mp(1, s))), pq.push(mp(0, mp(2, s)));
        else
            pq.push(mp(0, mp(0, s)));
    }

    while (!pq.empty()){
        pair<ll, ii> top = pq.top();
        pq.pop();

        int t = top.se.fi, u = top.se.se;
        ll d = top.fi;

        if (dis[t][u] != inf)
            continue;
        dis[t][u] = d;

        //printf("(%d, %d) -> %lld\n", t, u, d);

        for (int j = 0; j < adj[u].size(); j++){
            ii v = adj[u][j];
            if (t == 0){
                pq.push(mp(d+v.se, mp(0, v.fi)));
                if (best[v.fi])
                    pq.push(mp(d+v.se, mp(1, v.fi))), pq.push(mp(d+v.se, mp(2, v.fi)));
            }
            else if (t == 1){
                if (best[v.fi] && dis[4][u]-dis[4][v.fi] == v.se)
                    pq.push(mp(d, mp(1, v.fi)));
                else
                    pq.push(mp(d+v.se, mp(3, v.fi)));
            }
            else if (t == 2){
                if (best[v.fi] && dis[4][u]-dis[4][v.fi] == -v.se)
                    pq.push(mp(d, mp(2, v.fi)));
                else
                    pq.push(mp(d+v.se, mp(3, v.fi)));
            }
            else if (t == 3){
                pq.push(mp(d+v.se, mp(3, v.fi)));
            }
            else{
                pq.push(mp(d+v.se, mp(4, v.fi)));
            }
        }
    }
}

int main(){
    scanf("%d %d %d %d %d %d", &n, &m, &s1, &t1, &s2, &t2);
    for (int i = 0; i < m; i++){
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        adj[a].pb(mp(b, c));
        adj[b].pb(mp(a, c));
    }

    path(s1, 0);
    dfs(t1);
    path(s2, 1);

    ll ans = min(min(dis[0][t2], dis[1][t2]), min(dis[2][t2], dis[3][t2]));
    printf("%lld\n", ans);
    return 0;
}

Compilation message

commuter_pass.cpp: In function 'void dfs(int)':
commuter_pass.cpp:21:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j = 0; j < adj[u].size(); j++){
                     ~~^~~~~~~~~~~~~~~
commuter_pass.cpp: In function 'void path(int, int)':
commuter_pass.cpp:62:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < adj[u].size(); j++){
                         ~~^~~~~~~~~~~~~~~
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:92:10: 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, &s1, &t1, &s2, &t2);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:95:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d", &a, &b, &c);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	433 ms	15708 KB	Output is correct
2	Correct	469 ms	16768 KB	Output is correct
3	Correct	552 ms	24024 KB	Output is correct
4	Correct	428 ms	24024 KB	Output is correct
5	Correct	525 ms	24024 KB	Output is correct
6	Correct	422 ms	24024 KB	Output is correct
7	Correct	525 ms	24024 KB	Output is correct
8	Correct	486 ms	24024 KB	Output is correct
9	Correct	455 ms	24024 KB	Output is correct
10	Correct	487 ms	24024 KB	Output is correct
11	Correct	228 ms	24024 KB	Output is correct
12	Correct	495 ms	24024 KB	Output is correct

Subtask #2
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	515 ms	24024 KB	Output is correct
2	Correct	506 ms	24024 KB	Output is correct
3	Correct	793 ms	24024 KB	Output is correct
4	Correct	583 ms	24024 KB	Output is correct
5	Correct	541 ms	24024 KB	Output is correct
6	Correct	1022 ms	24024 KB	Output is correct
7	Correct	1024 ms	24024 KB	Output is correct
8	Correct	485 ms	24024 KB	Output is correct
9	Correct	532 ms	24024 KB	Output is correct
10	Correct	469 ms	24024 KB	Output is correct
11	Correct	325 ms	24024 KB	Output is correct
12	Correct	1002 ms	24024 KB	Output is correct

Subtask #3
0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	42 ms	24024 KB	Output is correct
2	Correct	4 ms	24024 KB	Output is correct
3	Correct	4 ms	24024 KB	Output is correct
4	Correct	59 ms	24024 KB	Output is correct
5	Correct	49 ms	24024 KB	Output is correct
6	Correct	5 ms	24024 KB	Output is correct
7	Incorrect	6 ms	24024 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

Subtask #4
0 / 45.0

#	결과	실행 시간	메모리	Grader output
1	Correct	433 ms	15708 KB	Output is correct
2	Correct	469 ms	16768 KB	Output is correct
3	Correct	552 ms	24024 KB	Output is correct
4	Correct	428 ms	24024 KB	Output is correct
5	Correct	525 ms	24024 KB	Output is correct
6	Correct	422 ms	24024 KB	Output is correct
7	Correct	525 ms	24024 KB	Output is correct
8	Correct	486 ms	24024 KB	Output is correct
9	Correct	455 ms	24024 KB	Output is correct
10	Correct	487 ms	24024 KB	Output is correct
11	Correct	228 ms	24024 KB	Output is correct
12	Correct	495 ms	24024 KB	Output is correct
13	Correct	515 ms	24024 KB	Output is correct
14	Correct	506 ms	24024 KB	Output is correct
15	Correct	793 ms	24024 KB	Output is correct
16	Correct	583 ms	24024 KB	Output is correct
17	Correct	541 ms	24024 KB	Output is correct
18	Correct	1022 ms	24024 KB	Output is correct
19	Correct	1024 ms	24024 KB	Output is correct
20	Correct	485 ms	24024 KB	Output is correct
21	Correct	532 ms	24024 KB	Output is correct
22	Correct	469 ms	24024 KB	Output is correct
23	Correct	325 ms	24024 KB	Output is correct
24	Correct	1002 ms	24024 KB	Output is correct
25	Correct	42 ms	24024 KB	Output is correct
26	Correct	4 ms	24024 KB	Output is correct
27	Correct	4 ms	24024 KB	Output is correct
28	Correct	59 ms	24024 KB	Output is correct
29	Correct	49 ms	24024 KB	Output is correct
30	Correct	5 ms	24024 KB	Output is correct
31	Incorrect	6 ms	24024 KB	Output isn't correct
32	Halted	0 ms	0 KB	-

답안 #52300

Compilation message

Subtask #1 16.0 / 16.0

Subtask #2 15.0 / 15.0

Subtask #3 0 / 24.0

Subtask #4 0 / 45.0

Subtask #1
16.0 / 16.0

Subtask #2
15.0 / 15.0

Subtask #3
0 / 24.0

Subtask #4
0 / 45.0