Submission #852164

#	Time	Username	Problem	Language	Result	Execution time	Memory
852164		lemonti	Commuter Pass (JOI18_commuter_pass)	C++14	31 / 100	383 ms	30520 KiB

commuter_pass

#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 (stderr)

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 / 16
• Subtask 2: 15 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 45