Submission #374643

#	Time	Username	Problem	Language	Result	Execution time	Memory
374643		MasterTaster	Commuter Pass (JOI18_commuter_pass)	C++14	15 / 100	1103 ms	42820 KiB

commuter_pass

#include <bits/stdc++.h>

#define pb push_back
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define xx first
#define yy second
#define MAXN 100010
#define INF 1000000000000000LL

using namespace std;

ll n, m, s, t, x, y, d[MAXN], p[MAXN];
vector<ll> g[MAXN];
map<pii, ll> w;

void dijkstra(int s)
{
    for (int i=1; i<=n; i++) { d[i]=INF; p[i]=-1; }

    priority_queue< pll, vector<pll>, greater<pll> > pq;
    pq.push({0, s});
    d[s]=0;
    p[s]=-1;

    while (!pq.empty())
    {
        ll td=pq.top().xx, u=pq.top().yy;
        pq.pop();

        if (td!=d[u]) continue;

        for (int i=0; i<g[u].size(); i++)
        {
            ll v, ww;
            v=g[u][i];
            pii par={u, v};
            ww=w[par];
            if (d[u]+ww<d[v])
            {
                d[v]=d[u]+ww;
                p[v]=u;
                pq.push({d[v], v});
            }
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin>>n>>m>>s>>t>>x>>y;

    for (int i=0; i<m; i++)
    {
        int u, v, ww; cin>>u>>v>>ww;
        g[u].pb(v);
        g[v].pb(u);
        w[{u, v}]=ww;
        w[{v, u}]=ww;
    }

    dijkstra(s);
    //cout<<d[1]<<" "<<d[2]<<" "<<d[3]<<" "<<d[4]<<" "<<d[5]<<" "<<d[6]<<endl;

    int u=t;
    while(p[u]!=-1)///p[u] ili u?
    {
        //cout<<u<<" "<<p[u]<<endl;
        w[{u, p[u]}]=0;
        w[{p[u], u}]=0;
        u=p[u];
    }


    dijkstra(x);
    //cout<<d[1]<<" "<<d[2]<<" "<<d[3]<<" "<<d[4]<<" "<<d[5]<<" "<<d[6];
    cout<<d[y];

}

Compilation message (stderr)

commuter_pass.cpp: In function 'void dijkstra(int)':
commuter_pass.cpp:34:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |         for (int i=0; i<g[u].size(); i++)
      |                       ~^~~~~~~~~~~~

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