Submission #852152

#	Time	Username	Problem	Language	Result	Execution time	Memory
852152		lemonti	Commuter Pass (JOI18_commuter_pass)	C++14	0 / 100	525 ms	34244 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;
#define int long long
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()
{
    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.we!=mx2[tmp.type][tmp.pos]) continue;
        for (auto it:V[tmp.pos])
        {
            node2 tt=tmp;
            if (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});
                }
                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});
                    }
                }
            }
            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:55:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   55 | main()
      | ^~~~

• Subtask 1: 0 / 16
• Subtask 2: 0 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 45