Submission #1230620

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230620		Jovica	Commuter Pass (JOI18_commuter_pass)	C++20	31 / 100	210 ms	21492 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
int const maxn = 1e5+1;
vector<vector<array<ll,2> > > adj(maxn);
ll n;
ll odS[maxn];
bool visited[maxn];

void djikstra(ll pocetok,ll kraj)
{
    priority_queue<array<ll,2>,vector<array<ll,2> > , greater<array<ll,2> > > pq;
    memset(visited,0,sizeof(visited));
    pq.push({0LL,pocetok});

    while (pq.size())
    {
        ll p = pq.top()[1],d = pq.top()[0];pq.pop();
        if (visited[p]) continue;
        visited[p] = true;
        odS[p] = d;
        if (p == kraj) return;

        for (auto a: adj[p])
        {
            if (visited[a[0]] == false) pq.push({d + a[1],a[0]});

        }
    }
}

bool pripagja[maxn];
void dfs(ll p,ll const kraj)
{
    pripagja[p] = true;
    if (p == kraj) return;
    for (auto s: adj[p])
    {
        if (odS[s[0]] + s[1] == odS[p] && pripagja[s[0]] == false) dfs(s[0],kraj);
    }
}

ll f(ll pocetok,ll kraj)
{
    priority_queue<array<ll,2>,vector<array<ll,2> > , greater<array<ll,2> > > pq;
    pq.push({0LL,pocetok});
    memset(visited,0,sizeof(visited));

    while(pq.size())
    {
        ll p = pq.top()[1],d = pq.top()[0];pq.pop();
        if (p == kraj) return d;
        if (visited[p]) continue;
        visited[p] = true;

        for (auto a: adj[p])
        {
            if (visited[a[0]] == false)
            {
                if (pripagja[p] && pripagja[a[0]] && max(odS[a[0]],odS[p]) - a[1] == min(odS[a[0]],odS[p])) pq.push({d,a[0]});
                else pq.push({d + a[1],a[0]});
            }
        }
    }
}

int main()
{
    ll m,s,t,pocetok,kraj;
    cin>>n>>m>>s>>t>>pocetok>>kraj;

    for (ll i=0;i<m;i++)
    {
        ll a,b,c;
        cin>>a>>b>>c;
        adj[a].push_back({b,c});
        adj[b].push_back({a,c});
    }

    djikstra(t,s);


    dfs(s,t);

    //for (ll i=1;i<=n;i++) cout<<odS[i]<<" "<<pripagja[i]<<endl;

    cout<<f(pocetok,kraj);
    return 0;
}
/*

5 6
1 3
1 5

1 2 1
2 3 1
1 4 1
4 3 1
1 5 2
5 3 1

*/

Compilation message (stderr)

commuter_pass.cpp: In function 'll f(ll, ll)':
commuter_pass.cpp:66:1: warning: control reaches end of non-void function [-Wreturn-type]
   66 | }
      | ^

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