Submission #398423

#	Time	Username	Problem	Language	Result	Execution time	Memory
398423		lukameladze	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	682 ms	28124 KiB

commuter_pass

# include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
using namespace std;
const int N=3e5+5;
long long n,m,u,vv,s,t,a,b,d[5][N],dist[N],dp[N],x,y,z,c,mn,ans;
priority_queue < pair <long long, long long> > q;
vector <pair <long long, long long > > v[N];
void go(int a, int ty) {
     while (!q.empty()) q.pop();
     for (int i=1; i<=n; i++) {
          d[ty][i]=1e17;
     }
     d[ty][a]=0;
     q.push({0,a});
     while (!q.empty()) {
          x=-(q.top().f);
          y=q.top().s;
          q.pop();
          if (d[ty][y]<x) continue;
          for (int i=0; i<v[y].size(); i++) {
               z=v[y][i].f;
               if (d[ty][z]>x+v[y][i].s) {
                    d[ty][z]=x+v[y][i].s;
                    q.push({-d[ty][z],z});
               }
          }
     }
}
void go1(int s,int c) {
     int fixx[N];
     for (int i=1; i<=n; i++) {
          dist[i]=1e17;
          fixx[i]=0;
          dp[i]=d[2][i];
     }
     dist[s]=0;
     fixx[s]=1;
     q.push({0,s});
     while(!q.empty()) {
          x=-(q.top().f);
          y=q.top().s;
          q.pop();
          if (dist[y]<x) continue;
          for (int i=0; i<v[y].size(); i++) {
               if (dist[y]+v[y][i].s+d[c][v[y][i].f]==mn) {
                fixx[v[y][i].f]=1;
                fixx[y]=1;
                    dp[v[y][i].f]=min(dp[v[y][i].f],dp[y]);
               }
               if (dist[v[y][i].f]>dist[y]+v[y][i].s){
                    dist[v[y][i].f]=dist[y]+v[y][i].s;
                    q.push({-dist[v[y][i].f],v[y][i].f});
               }
          }
     }
     for (int i=1; i<=n; i++) {
          if (!fixx[i]) continue;
          ans=min(ans,dp[i]+d[1][i]);
     }
     
}
int main(){
     cin>>n>>m;
     cin>>s>>t>>u>>vv;
     for (int i=1; i<=m; i++) {
          cin>>a>>b>>c;
          v[a].pb({b,c});
          v[b].pb({a,c});
     }
     go(u,1);
     go(vv,2);
     go(t,3);
     go(s,4);
     mn=d[3][s];
     ans=1e17;
     go1(s,3);
     go1(t,4);
     cout<<min(ans,d[1][vv])<<endl;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void go(int, int)':
commuter_pass.cpp:22:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int>, std::allocator<std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |           for (int i=0; i<v[y].size(); i++) {
      |                         ~^~~~~~~~~~~~
commuter_pass.cpp: In function 'void go1(int, int)':
commuter_pass.cpp:46:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int>, std::allocator<std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |           for (int i=0; i<v[y].size(); i++) {
      |                         ~^~~~~~~~~~~~

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