Submission #167708

#	Time	Username	Problem	Language	Result	Execution time	Memory
167708		theStaticMind	Commuter Pass (JOI18_commuter_pass)	C++14	15 / 100	583 ms	262148 KiB

commuter_pass

#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define ii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define INF 100000000000000000
#define modulo 1000000007
#define mod 998244353
#define int long long int
using namespace std;
vector<ii>adj[100005];
struct Shortest_path{
      vector<int>val;
      int start;
      Shortest_path(){}
      Shortest_path(int n,int s){
            start=s;
            val.resize(n,INF);
            val[s]=0;
            vector<bool>vis(n,false);
            priority_queue<ii,vector<ii>,greater<ii>>Q;
            Q.push({0,s});
            while(!Q.empty()){
                  int x=Q.top().second;Q.pop();
                  if(vis[x])continue;
                  vis[x]=true;
                  for(int i=0;i<adj[x].size();i++){
                        int y=adj[x][i].first,z=adj[x][i].second;
                        if(vis[y]||val[y]<=val[x]+z)continue;
                        val[y]=val[x]+z;
                        Q.push({val[y],y});
                  }
            }
      }
};
Shortest_path comm;
Shortest_path data1;
Shortest_path data2;
vector<int> path[100005];
vector<int> indeg(100005,0);
vector<ii>dp[100005];
int ans=INF;
void dfs(int x){
      for(int i=0;i<dp[x].size();i++){
            dp[x][i].first=min(dp[x][i].first,data1.val[x]);
            dp[x][i].second=min(dp[x][i].second,data2.val[x]);
            ans=min(ans,dp[x][i].first+dp[x][i].second);
      }
      for(int i=0;i<path[x].size();i++){
            int y=path[x][i];
            indeg[y]--;
  //          if(dp[y].size()<dp[x].size())swap(dp[x],dp[y]);
            for(int j=0;j<dp[x].size();j++){
                  dp[y].pb(dp[x][j]);
            }
            if(indeg[y]==0)dfs(y);
      }
}
int32_t main(){
      ios_base::sync_with_stdio(false);
      cin.tie(NULL);
   //   freopen("q.gir","r",stdin);
   //   freopen("q.cik","w",stdout);
      int n,m,S,T,U,V;
      cin>>n>>m>>S>>T>>U>>V;swap(S,T);
      for(int i=0;i<m;i++){
            int a,b,c;
            cin>>a>>b>>c;
            adj[a].pb({b,c});
            adj[b].pb({a,c});
      }
      comm=Shortest_path(n+1,S);
      data1=Shortest_path(n+1,U);
      data2=Shortest_path(n+1,V);
      ans=data1.val[V];
      queue<int>Q;
      vector<bool>vis(n+1,false);
      Q.push(T);
      while(!Q.empty()){
            int x=Q.front();
            Q.pop();
            if(vis[x])continue;
            vis[x]=true;
            for(int i=0;i<adj[x].size();i++){
                  int y=adj[x][i].first,z=adj[x][i].second;
                  if(comm.val[x]==comm.val[y]+z){
                        Q.push(y);
                        path[x].pb(y);
                        indeg[y]++;
                  }
            }
      }
      dp[T].pb({INF,INF});
      dfs(T);
      cout<<ans;
}

Compilation message (stderr)

commuter_pass.cpp: In constructor 'Shortest_path::Shortest_path(long long int, long long int)':
commuter_pass.cpp:27:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                   for(int i=0;i<adj[x].size();i++){
                               ~^~~~~~~~~~~~~~
commuter_pass.cpp: In function 'void dfs(long long int)':
commuter_pass.cpp:44:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i=0;i<dp[x].size();i++){
                   ~^~~~~~~~~~~~~
commuter_pass.cpp:49:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i=0;i<path[x].size();i++){
                   ~^~~~~~~~~~~~~~~
commuter_pass.cpp:53:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j=0;j<dp[x].size();j++){
                         ~^~~~~~~~~~~~~
commuter_pass.cpp: In function 'int32_t main()':
commuter_pass.cpp:84:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i=0;i<adj[x].size();i++){
                         ~^~~~~~~~~~~~~~

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