Submission #1032991

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032991		2zzz	Commuter Pass (JOI18_commuter_pass)	C++14	31 / 100	237 ms	31592 KiB

commuter_pass

#include<bits/stdc++.h>
using namespace std;

#define ii pair < int , int >
#define iii pair < int , ii > 
#define int long long

const int N = 1e5 + 5;
int n , m , s , t , u , v;
vector < ii > g[N];
priority_queue < iii , vector < iii > , greater < iii > > q;
int dists[N] , distt[N] , dist[N][5];

void dijkstra(int start , int dist[N])
{
   priority_queue < ii , vector < ii > , greater < ii > > q;
   while(!q.empty())
      q.pop();
   for(int i = 1 ; i <= n ; i++)
      dist[i] = 1e18;
   dist[start] = 0;
   q.push(ii(dist[start] , start));
   while(!q.empty())
   {
      int u = q.top().second;
      int cost = q.top().first;
      q.pop();
      if(cost > dist[u])
         continue;
      for(auto e: g[u])
      {
         int v = e.first;
         int w = e.second;
         if(dist[v] > dist[u] + w)
         {
            dist[v] = dist[u] + w;
            q.push(ii(dist[v] , v));
         }
      }
   }
}

void dijkstra2(int start)
{
   for(int i = 1 ; i <= n ; i++)
      for(int j = 0 ; j <= 2 ; j++)
         dist[i][j] = 1e18;
   dist[start][0] = 0;
   q.push(iii(dist[start][0] , ii(start , 0)));
   while(!q.empty())
   {
      int u = q.top().second.first;
      int k = q.top().second.second;
      int cost = q.top().first;
      //cout << u << " " << k << " " << cost << endl;
      q.pop();
      if(cost > dist[u][k])
         continue;
      if(u == v)
      {
         cout << dist[v][k];
         exit(0);
      }
      if(k == 0)
      {
         for(auto e: g[u])
         {
            int v = e.first;
            int w = e.second;
            if(dist[v][k] > dist[u][k] + w)
            {
               dist[v][k] = dist[u][k] + w;
               q.push(iii(dist[v][k] , ii(v , k)));
            }
            if(dists[u] + w + distt[v] == dists[t]
            || dists[v] + w + distt[u] == dists[t])
            {
               if(dist[v][k + 1] > dist[u][k])
               {
                  dist[v][k + 1] = dist[u][k];
                  q.push(iii(dist[v][k + 1] , ii(v , k + 1)));
               }
            }
         }
      }
      else if(k == 1)
      {
         for(auto e: g[u])
         {
            int v = e.first;
            int w = e.second;
            if(dist[v][k + 1] > dist[u][k] + w)
            {
               dist[v][k + 1] = dist[u][k] + w;
               q.push(iii(dist[v][k + 1] , ii(v , k + 1)));
            }
            if(dists[u] + w + distt[v] == dists[t]
            || dists[v] + w + distt[u] == dists[t])
            {
               if(dist[v][k] > dist[u][k])
               {
                  dist[v][k] = dist[u][k];
                  q.push(iii(dist[v][k] , ii(v , k)));
               }
            }
         }
      }
      else
      {
         for(auto e: g[u])
         {
            int v = e.first;
            int w = e.second;
            if(dist[v][k] > dist[u][k] + w)
            {
               dist[v][k] = dist[u][k] + w;
               q.push(iii(dist[v][k] , ii(v , k)));
            }
         }
      }
   }
}

main()
{
   ios::sync_with_stdio(0);
   cin.tie(0);
   cin >> n >> m;
   cin >> s >> t;
   cin >> u >> v;
   for(int i = 1 ; i <= m ; i++)
   {
      int u , v , w;
      cin >> u >> v >> w;
      g[u].push_back(ii(v , w));
      g[v].push_back(ii(u , w));
   }
   dijkstra(s , dists);
   dijkstra(t , distt);
   dijkstra2(u);
}

Compilation message (stderr)

commuter_pass.cpp:124:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  124 | main()
      | ^~~~

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