Submission #922090

#	Time	Username	Problem	Language	Result	Execution time	Memory
922090		Aiperiii	Commuter Pass (JOI18_commuter_pass)	C++14	15 / 100	699 ms	42296 KiB

commuter_pass

#include <bits/stdc++.h>
#define int long long
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
using namespace std;
const int N=1e5+5;
vector <pair <int,int> > g[N];
signed main(){
   int n,m,s,t,u,w;
   cin>>n>>m>>s>>t>>u>>w;
   for(int i=0;i<m;i++){
      int a,b,c;
      cin>>a>>b>>c;
      g[a].pb({b,c});
      g[b].pb({a,c});
   }
   set <pair <int,int> > st;
   st.insert({0,s});
   vector <int> d(n+1,1e18),p(n+1);
   d[s]=0;
   while(!st.empty()){
      int v=st.begin()->second;
      st.erase(st.begin());
      for(auto to : g[v]){
         if(d[to.ff]>d[v]+to.ss){
            st.erase({d[to.ff],to.ff});
            d[to.ff]=d[v]+to.ss;
            st.insert({d[to.ff],to.ff});
            p[to.ff]=v;
         }
      }
   }
   vector <int> path;
   path.pb(t);
   while(t!=s){
      t=p[t];
      path.pb(t);
   }
   map <pair <int,int> ,int> vis;
   for(int i=0;i<path.size()-1;i++){
      vis[{path[i],path[i+1]}]=1;
      vis[{path[i+1],path[i]}]=1;
   }
   for(int i=1;i<=n;i++){
      d[i]=1e18;
   }
   d[u]=0;
   st.insert({0,u});
   while(!st.empty()){
      int v=st.begin()->second;
      st.erase(st.begin());
      for(auto to : g[v]){
         if(d[to.ff]>d[v]+to.ss){
            if(vis[{to.ff,v}]==1 or vis[{v,to.ff}]==1)to.ss=0;
            st.erase({d[to.ff],to.ff});
            d[to.ff]=d[v]+to.ss;
            st.insert({d[to.ff],to.ff});
            p[to.ff]=v;
         }
      }
   }
   cout<<d[w]<<"\n";
}
/*
6 6
1 6
1 4
1 2 1
2 3 1
3 5 1
2 4 3
4 5 2
5 6 1
 
6 5
1 2
3 6
1 2 1000000000
2 3 1000000000
3 4 1000000000
4 5 1000000000
5 6 1000000000
 */

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:42:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |    for(int i=0;i<path.size()-1;i++){
      |                ~^~~~~~~~~~~~~~

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