Submission #167721

#	Time	Username	Problem	Language	Result	Execution time	Memory
167721		theStaticMind	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	556 ms	32160 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<int>dp(100005,INF);
int ans=INF;
void dfs(int x){
      dp[x]=min(dp[x],data1.val[x]);
      ans=min(ans,dp[x]+data2.val[x]);
      for(int i=0;i<path[x].size();i++){
            int y=path[x][i];
            indeg[y]--;
            dp[y]=min(dp[y],dp[x]);
            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;
      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]++;
                  }
            }
      }
      dfs(T);
      dp=vector<int>(100005,INF);
      indeg=vector<int>(100005,0);
      vector<int> rpath[100005];
      for(int i=0;i<=n;i++){
            for(int j=0;j<path[i].size();j++){
                  rpath[path[i][j]].pb(i);
                  indeg[i]++;
            }
      }
      for(int i=0;i<=n;i++)path[i]=rpath[i];
      dfs(S);
      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:46:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i=0;i<path[x].size();i++){
                   ~^~~~~~~~~~~~~~~
commuter_pass.cpp: In function 'int32_t main()':
commuter_pass.cpp:78:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i=0;i<adj[x].size();i++){
                         ~^~~~~~~~~~~~~~
commuter_pass.cpp:92:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j=0;j<path[i].size();j++){
                         ~^~~~~~~~~~~~~~~

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