oj.uz

답안 #852164

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
852164 2023-09-21T11:02:11 Z lemonti Commuter Pass (JOI18_commuter_pass) C++14
31 / 100
 383 ms 30520 KB 
#include <bits/stdc++.h>

using namespace std;
#define int long long
#define INT_MAX LLONG_MAX
int mx[2][100001];
int mx2[2][100001];
struct node
{
    int pos,we;
    node (int a,int b)
    {
        pos=a;
        we=b;
    }
};
struct node2
{
    int pos,we,rwe,st,type;
    node2 (int a,int b,int c,int d,int e)
    {
        pos=a;
        we=b;
        rwe=c;
        st=d;
        type=e;
    }
};
bool cmp2(node2 x,node2 y)
{
    return x.we>y.we;
}
bool cmp(node x,node y)
{
    return x.we>y.we;
}
void dij(int type,int st,vector<vector<pair<int,int>>> &v)
{
    priority_queue<node,vector<node>,function<bool(node,node)>> p(cmp);
    p.push({st,0});
    mx[type][st]=0;
    while (p.empty()==false)
    {
        node tmp=p.top();p.pop();
        if (tmp.we!=mx[type][tmp.pos]) continue;
        for (auto it:v[tmp.pos])
        {
            if (it.second+tmp.we<mx[type][it.first])
            {
                mx[type][it.first]=it.second+tmp.we;
                p.push({it.first,mx[type][it.first]});
            }
        }
    }
}
main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //freopen("TEST.INP","r",stdin);
    //freopen("TEST.OUT","w",stdout);
    int n,m;
    cin>>n>>m;
    int s,t;
    cin>>s>>t;
    int u,v;
    cin>>u>>v;
    vector<vector<pair<int,int>>> V(n+1);
    for (int i=0;i<m;i++)
    {
        int x,y,w;
        cin>>x>>y>>w;
        V[x].push_back({y,w});
        V[y].push_back({x,w});
    }
    for (int i=1;i<=n;i++)
    {
        mx2[1][i]=mx2[0][i]=mx[1][i]=mx[0][i]=INT_MAX;
    }
    dij(1,s,V);
    dij(0,t,V);
    priority_queue<node2,vector<node2>,function<bool(node2,node2)>> pr(cmp2);
    pr.push({u,0,0,0,1});
    pr.push({u,0,0,u,0});
    mx2[0][u]=0;
    mx2[1][u]=0;
    while (pr.empty()==false)
    {
        node2 tmp=pr.top();pr.pop();
        if (tmp.type&&tmp.we!=mx2[tmp.type][tmp.pos]) continue;
        else if (!tmp.st&&tmp.we!=mx2[tmp.type][tmp.pos]) continue;
        for (auto it:V[tmp.pos])
        {
            node2 tt=tmp;
            if (tt.type)
            {
                if (it.second+mx[1][tmp.pos]+mx[0][it.first]==mx[1][t]||it.second+mx[0][tmp.pos]+mx[1][it.first]==mx[1][t])
                {
                    tt.type=0;
                    tt.st=tt.pos;
                    tt.rwe=it.second;
                    if (tt.we<mx2[tt.type][it.first])
                    {
                        mx2[tt.type][it.first]=tt.we;
                        pr.push({it.first,tt.we,tt.rwe,tt.st,tt.type});
                    }
                }
                if (tt.we+it.second<mx2[tt.type][it.first])
                {
                    mx2[tt.type][it.first]=tt.we+it.second;
                    pr.push({it.first,tt.we+it.second,0,0,tt.type});
                }
            }
            else
            {
                if (tt.we+it.second<mx2[tt.type][it.first])
                {
                    mx2[tt.type][it.first]=tt.we+it.second;
                    pr.push({it.first,tt.we+it.second,0,0,tt.type});
                }
                if ((it.second+tt.rwe+mx[1][tt.st]+mx[0][it.first]==mx[1][t]||it.second+tt.rwe+mx[1][it.first]+mx[0][tt.st]==mx[1][t])&&tt.st)
                {
                    if (tmp.we<mx2[tmp.type][it.first])
                    {
                        mx2[tmp.type][it.first]=tt.we;
                        pr.push({it.first,tt.we,tt.rwe+it.second,tt.st,tt.type});
                    }
                }
            }
        }
    }
    cout<<min(mx2[0][v],mx2[1][v]);
}

Compilation message

commuter_pass.cpp:5: warning: "INT_MAX" redefined
    5 | #define INT_MAX LLONG_MAX
      | 
In file included from /usr/include/c++/10/climits:42,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:39,
                 from commuter_pass.cpp:1:
/usr/lib/gcc/x86_64-linux-gnu/10/include/limits.h:120: note: this is the location of the previous definition
  120 | #define INT_MAX __INT_MAX__
      | 
commuter_pass.cpp:56:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   56 | main()
      | ^~~~

Subtask #1
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 331 ms 30520 KB Output is correct
2 Correct 322 ms 22756 KB Output is correct
3 Correct 329 ms 24548 KB Output is correct
4 Correct 340 ms 23704 KB Output is correct
5 Correct 316 ms 23344 KB Output is correct
6 Correct 375 ms 29988 KB Output is correct
7 Correct 351 ms 24336 KB Output is correct
8 Correct 296 ms 22812 KB Output is correct
9 Correct 281 ms 23620 KB Output is correct
10 Correct 207 ms 24624 KB Output is correct
11 Correct 92 ms 13772 KB Output is correct
12 Correct 320 ms 24480 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 314 ms 23720 KB Output is correct
2 Correct 363 ms 24304 KB Output is correct
3 Correct 365 ms 28292 KB Output is correct
4 Correct 354 ms 22664 KB Output is correct
5 Correct 344 ms 23708 KB Output is correct
6 Correct 324 ms 24528 KB Output is correct
7 Correct 359 ms 28788 KB Output is correct
8 Correct 361 ms 24076 KB Output is correct
9 Correct 383 ms 24784 KB Output is correct
10 Correct 346 ms 23428 KB Output is correct
11 Correct 111 ms 15060 KB Output is correct
12 Correct 341 ms 24484 KB Output is correct

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 3928 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 11 ms 5464 KB Output is correct
5 Correct 6 ms 3928 KB Output is correct
6 Correct 1 ms 2648 KB Output is correct
7 Incorrect 2 ms 2648 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 331 ms 30520 KB Output is correct
2 Correct 322 ms 22756 KB Output is correct
3 Correct 329 ms 24548 KB Output is correct
4 Correct 340 ms 23704 KB Output is correct
5 Correct 316 ms 23344 KB Output is correct
6 Correct 375 ms 29988 KB Output is correct
7 Correct 351 ms 24336 KB Output is correct
8 Correct 296 ms 22812 KB Output is correct
9 Correct 281 ms 23620 KB Output is correct
10 Correct 207 ms 24624 KB Output is correct
11 Correct 92 ms 13772 KB Output is correct
12 Correct 320 ms 24480 KB Output is correct
13 Correct 314 ms 23720 KB Output is correct
14 Correct 363 ms 24304 KB Output is correct
15 Correct 365 ms 28292 KB Output is correct
16 Correct 354 ms 22664 KB Output is correct
17 Correct 344 ms 23708 KB Output is correct
18 Correct 324 ms 24528 KB Output is correct
19 Correct 359 ms 28788 KB Output is correct
20 Correct 361 ms 24076 KB Output is correct
21 Correct 383 ms 24784 KB Output is correct
22 Correct 346 ms 23428 KB Output is correct
23 Correct 111 ms 15060 KB Output is correct
24 Correct 341 ms 24484 KB Output is correct
25 Correct 6 ms 3928 KB Output is correct
26 Correct 1 ms 2392 KB Output is correct
27 Correct 1 ms 2392 KB Output is correct
28 Correct 11 ms 5464 KB Output is correct
29 Correct 6 ms 3928 KB Output is correct
30 Correct 1 ms 2648 KB Output is correct
31 Incorrect 2 ms 2648 KB Output isn't correct
32 Halted 0 ms 0 KB -