Submission #401610

#	Time	Username	Problem	Language	Result	Execution time	Memory
401610		wildturtle	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	694 ms	26100 KiB

commuter_pass

#include<bits/stdc++.h>
#define ll long long
#define f first
#define sc second
#define pb push_back
using namespace std;
ll a,b,c,d,i,e,f,g,n,m,k,l,ans,t,s,u,v1;
ll dist[5][100005],dist1[100005],fix[100005],dp[100005];
vector < pair < ll , ll > > v[200005];
priority_queue < pair <ll,ll> > pq;
void dijkstra(ll x,ll y) {
    for(ll i=1;i<=n;i++) {
        dist[y][i]=1e18;
    }
    dist[y][x]=0;
    pq.push({0,x});
    while(pq.size()) {
        a=-pq.top().f;
        b=pq.top().sc;
        pq.pop();
        for(ll i=0;i<v[b].size();i++) {
            if(dist[y][v[b][i].f]>a+v[b][i].sc) {
                dist[y][v[b][i].f]=a+v[b][i].sc;
                pq.push({-dist[y][v[b][i].f],v[b][i].f});
            }
        }
    }
}
void dijkstra1(ll x,ll y) {
    for(ll i=1;i<=n;i++) {
        dist1[i]=1e18;
        fix[i]=0;
        dp[i]=dist[3][i];
    }
    dist1[x]=0;
    fix[x]=1;
    pq.push({0,x});
    while(pq.size()) {
        a=-pq.top().f;
        b=pq.top().sc;
        pq.pop();
        for(ll i=0;i<v[b].size();i++) {
            if(dist1[b]+v[b][i].sc+dist[y][v[b][i].f]==dist[1][t]) {
                fix[b]=1; fix[v[b][i].f]=1;
                dp[v[b][i].f]=min(dp[v[b][i].f],dp[b]);
            }
            if(dist1[v[b][i].f]>a+v[b][i].sc) {
                dist1[v[b][i].f]=a+v[b][i].sc;
                pq.push({-dist1[v[b][i].f],v[b][i].f});
            }
        }
    }    
    for(ll i=1;i<=n;i++) {
        if(fix[i]==0) continue;
        ans=min(ans,dp[i]+dist[4][i]);
    }
}
int main() {
    cin>>n>>m>>s>>t>>u>>v1;
    for(ll i=1;i<=m;i++) {
        cin>>a>>b>>c;
        v[a].pb({b,c});
        v[b].pb({a,c});
    }
    ans=1e18;
    dijkstra(s,1); dijkstra(t,2); dijkstra(u,3); dijkstra(v1,4);
    dijkstra1(s,2); dijkstra1(t,1);
    
    cout<<min(ans,dist[3][v1]);
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void dijkstra(long long int, long long int)':
commuter_pass.cpp:21:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |         for(ll i=0;i<v[b].size();i++) {
      |                    ~^~~~~~~~~~~~
commuter_pass.cpp: In function 'void dijkstra1(long long int, long long int)':
commuter_pass.cpp:42:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         for(ll i=0;i<v[b].size();i++) {
      |                    ~^~~~~~~~~~~~

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