제출 #765419

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
765419		vjudge1	Commuter Pass (JOI18_commuter_pass)	C++17	15 / 100	1128 ms	46048 KiB

commuter_pass

/**
  * Author: Amirrrr
  * Created: 24.06.2023
  * Why am I so stupid? :c
  * Slishkom slab
**/

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

#define int long long
#define pb push_back
#define all(x) x.begin(), x.end()
#define FF first
#define SS second
#define ent "\n"
#define int long long

const int N = 2e5 + 13;
const int MOD = 1e9 + 7;
const int INF = 1e18;

int n,m,s,t,u,v,pr[N],ans[N],ans1[N];
vector<pair<int,int>>g[N];

void gogo (){
    cin>>n>>m;
    cin>>s>>t>>u>>v;
    map<pair<int,int>,int>mp;
    for(int i=1;i<=m;i++){
        int x,y,val;cin>>x>>y>>val;
        g[x].pb({y,val}),g[y].pb({x,val});
        mp[{x,y}]=val;
        mp[{y,x}]=val;
    }
    for(int i=1;i<=n;i++)ans[i]=INF,ans1[i]=INF;
    set<pair<int,int>>st;
    vector<int>dst;
    st.insert({0,s});
    ans[s]=0;
    while(st.size()){
        pair<int,int>v=*(st.begin());
        st.erase(st.begin());
        for(auto to:g[v.SS]){
            int cur=ans[v.SS]+mp[{to.FF,v.SS}];
            if(ans[to.FF]>cur){
                st.erase({ans[to.FF],to.FF});
                ans[to.FF]=cur;
                st.insert({cur,to.FF});
                pr[to.FF]=v.SS;
            }
        }
    }
    int ok=t;
    while(ok){
        dst.pb(ok);
        ok=pr[ok];
    }
    for(int i=0;i+1<dst.size();i++){
        mp[{dst[i],dst[i+1]}]=0,mp[{dst[i+1],dst[i]}]=0;
    }
    st.insert({0,u});
    ans1[u]=0;
    while(st.size()){
        pair<int,int>v=*(st.begin());
        st.erase(st.begin());
        for(auto to:g[v.SS]){
            int cur=ans1[v.SS]+mp[{to.FF,v.SS}];
            if(ans1[to.FF]>cur){
                st.erase({ans1[to.FF],to.FF});
                ans1[to.FF]=cur;
                st.insert({cur,to.FF});
            }
        }
    }
    cout<<ans1[v];
}

signed main (/*Amir Mirmanov*/){
    ios_base::sync_with_stdio(0),cin.tie(0);
    int Q = 1,test = 1;
    //freopen("herding.in","r",stdin);
	//freopen("herding.out","w",stdout);
   // cin >> Q;
    while (Q --){
        gogo ();
    }
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

commuter_pass.cpp: In function 'void gogo()':
commuter_pass.cpp:59:20: 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]
   59 |     for(int i=0;i+1<dst.size();i++){
      |                 ~~~^~~~~~~~~~~
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:81:15: warning: unused variable 'test' [-Wunused-variable]
   81 |     int Q = 1,test = 1;
      |               ^~~~

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