oj.uz

답안 #854414

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
854414 2023-09-27T13:02:14 Z how2read Commuter Pass (JOI18_commuter_pass) C++14
31 / 100
 311 ms 28080 KB 
#include <bits/stdc++.h>

using namespace std;
int n,m,S,T,U,V;
vector<pair<int,long long>> edge[100005];
long long ds[100005], dt[100005], du[100005][2][2], dv[100005][2][2];

struct hi {
    int x;
    long long v;
    int free;
    int check;
};

bool operator > (const hi& x1, const hi& x2)
{
    return x1.v > x2.v;
}
bool operator < (const hi& x1, const hi& x2)
{
    return x1.v < x2.v;
}

void dij(int s, long long d[100005])
{
    priority_queue<pair<long long,int>, vector<pair<long long, int>>, greater<pair<long long, int>> > q;
    q.push({0,s});
    for(int i=1;i<=n;i++)
        d[i] = LLONG_MAX;
    d[s] = 0;

    while(q.size() > 0)
    {
        int x = q.top().second;
        long long vx = q.top().first;
        q.pop();

        if(d[x] < vx)
            continue;

        for(auto i : edge[x])
        {
            int v = i.first;
            int vv = i.second;

            if(d[v] > d[x] + vv)
            {
                d[v] = d[x] + vv;
                q.push({d[v], v});
            }
        }
    }
}

void doo(int s, int t, long long d[100005][2][2])
{
    priority_queue<hi, vector<hi>, greater<hi>> q;
    q.push({s,0,0,0});
    for(int i=1;i<=n;i++)
    {
        d[i][0][0] = LLONG_MAX;
        d[i][1][0] = LLONG_MAX;
        d[i][0][1] = LLONG_MAX;
    }
    d[s][0][0] = 0;
    d[s][1][0] = 0;
    d[s][0][1] = 0;

    while(q.size() > 0)
    {
        int x = q.top().x;
        long long vx = q.top().v;
        int free = q.top().free;
        int check = q.top().check;
        q.pop();

        if(vx > d[x][free][check])
            continue;

        if(x == t)
            return;

        for(auto i : edge[x])
        {
            int v = i.first;
            int vv = i.second;

            if(d[v][0][check] > d[x][free][check] + vv)
            {
                d[v][0][check] = d[x][free][check] + vv;
                q.push({v, d[v][0][check], 0, check});
            }

            if(check == 1)
                continue;

            if(ds[x] + vv + dt[v] == ds[T])
            {
                if(d[v][1][0] > d[x][free][check])
                {
                    d[v][1][0] = d[x][free][check];
                    q.push({v, d[v][1][0], 1, 0});
                }
                else if(free == 1)
                {
                    if(d[v][0][1] > d[x][free][check] + vv)
                    {
                        d[v][0][1] = d[x][free][check] + vv;
                        q.push({v, d[v][0][1], 0, 1});
                    }
                }
            }
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>m;
    cin>>S>>T>>U>>V;
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        edge[x].push_back({y,z});
        edge[y].push_back({x,z});
    }

    dij(S,ds);
    dij(T,dt);
    doo(U,V,du);
    doo(V,U,dv);

    long long res = min(du[V][0][0], dv[U][0][0]);
    res = min(res,min(du[V][1][0], dv[U][1][0]));
    res = min(res, min(du[V][0][1], dv[U][0][1]));
    cout<<res;

    return 0;
}

Subtask #1
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 161 ms 23864 KB Output is correct
2 Correct 311 ms 26564 KB Output is correct
3 Correct 225 ms 28080 KB Output is correct
4 Correct 171 ms 22444 KB Output is correct
5 Correct 280 ms 27204 KB Output is correct
6 Correct 173 ms 23952 KB Output is correct
7 Correct 262 ms 25560 KB Output is correct
8 Correct 200 ms 26868 KB Output is correct
9 Correct 160 ms 23252 KB Output is correct
10 Correct 128 ms 22384 KB Output is correct
11 Correct 76 ms 15816 KB Output is correct
12 Correct 175 ms 23544 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 145 ms 23716 KB Output is correct
2 Correct 205 ms 26480 KB Output is correct
3 Correct 213 ms 25524 KB Output is correct
4 Correct 276 ms 24120 KB Output is correct
5 Correct 208 ms 26540 KB Output is correct
6 Correct 212 ms 26692 KB Output is correct
7 Correct 223 ms 26496 KB Output is correct
8 Correct 269 ms 27040 KB Output is correct
9 Correct 162 ms 24912 KB Output is correct
10 Correct 171 ms 24120 KB Output is correct
11 Correct 83 ms 17612 KB Output is correct
12 Correct 216 ms 26792 KB Output is correct

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 9820 KB Output is correct
2 Correct 3 ms 8284 KB Output is correct
3 Correct 3 ms 8408 KB Output is correct
4 Correct 13 ms 11164 KB Output is correct
5 Correct 7 ms 9820 KB Output is correct
6 Correct 2 ms 8284 KB Output is correct
7 Incorrect 3 ms 8372 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 161 ms 23864 KB Output is correct
2 Correct 311 ms 26564 KB Output is correct
3 Correct 225 ms 28080 KB Output is correct
4 Correct 171 ms 22444 KB Output is correct
5 Correct 280 ms 27204 KB Output is correct
6 Correct 173 ms 23952 KB Output is correct
7 Correct 262 ms 25560 KB Output is correct
8 Correct 200 ms 26868 KB Output is correct
9 Correct 160 ms 23252 KB Output is correct
10 Correct 128 ms 22384 KB Output is correct
11 Correct 76 ms 15816 KB Output is correct
12 Correct 175 ms 23544 KB Output is correct
13 Correct 145 ms 23716 KB Output is correct
14 Correct 205 ms 26480 KB Output is correct
15 Correct 213 ms 25524 KB Output is correct
16 Correct 276 ms 24120 KB Output is correct
17 Correct 208 ms 26540 KB Output is correct
18 Correct 212 ms 26692 KB Output is correct
19 Correct 223 ms 26496 KB Output is correct
20 Correct 269 ms 27040 KB Output is correct
21 Correct 162 ms 24912 KB Output is correct
22 Correct 171 ms 24120 KB Output is correct
23 Correct 83 ms 17612 KB Output is correct
24 Correct 216 ms 26792 KB Output is correct
25 Correct 7 ms 9820 KB Output is correct
26 Correct 3 ms 8284 KB Output is correct
27 Correct 3 ms 8408 KB Output is correct
28 Correct 13 ms 11164 KB Output is correct
29 Correct 7 ms 9820 KB Output is correct
30 Correct 2 ms 8284 KB Output is correct
31 Incorrect 3 ms 8372 KB Output isn't correct
32 Halted 0 ms 0 KB -