제출 #833421

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

commuter_pass

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n, m, s, t, u, v, a, b, c, now;
vector<pair<int,ll>> edges[100002], ve[100002];
const ll INF=1e18;
void prim(){
    vector<ll> dist(n+2, INF);
    vector<bool> vis(n+2, false);
    vector<pair<int,ll>> pred(n+2);
    priority_queue<pair<ll, int>, vector<pair<ll,int>>, greater<pair<ll,int>>> pq;

    for(int i=1; i<=n; i++) pred[i].first=-1;
    dist[s]=0;
    pq.push({0, s});
    while(!pq.empty()){
        now=pq.top().second;
        pq.pop();
        if(!vis[now]){
            vis[now]=true;
            for(auto i: edges[now]){
                if(dist[i.first] > i.second && !vis[i.first]){
                    dist[i.first]=i.second;
                    pred[i.first]={now, dist[i.first]};
                    pq.push({dist[i.first], i.first});
                }
            }
        }
    }
    for(int i=1; i<=n; i++){
        // cout<<i<<" "<<pred[i].first<<" "<<pred[i].second<<"\n";
        if(pred[i].first != -1){
            ve[i].push_back(pred[i]);
            ve[pred[i].first].push_back({i, pred[i].second});
        }
    }
    for(int i=1; i<=n; i++){
        if(ve[i].size()>1) sort(ve[i].begin(), ve[i].end());
        if(edges[i].size()>1) sort(edges[i].begin(), edges[i].end());
    }
}
void bfs(int awal, int akhir){
    queue<int> q;
    vector<bool> vis(n+2, false);
    vector<int> d(n+2, -1);
    q.push(awal);
    vis[awal]=true;
    while(!q.empty()){
        now=q.front();
        q.pop();
        if(now == akhir) break;
        for(auto i: ve[now]){
            if(!vis[i.first]){
                vis[i.first]=true;
                q.push(i.first);
                d[i.first]=now;
            }
        }
    }
    now=akhir;
    int l, r, m;
    while(d[now] != -1){
        l=0;
        r=ve[now].size()-1;
        while(l <= r){
            m=(l+r)/2;
            if(ve[now][m].first == d[now]){
                ve[now][m].second=0;
                break;
            }
            else if(ve[now][m].first > d[now]) r=m-1;
            else l=m+1;
        }
        l=0;
        r=ve[d[now]].size()-1;
        while(l <= r){
            m=(l+r)/2;
            if(ve[d[now]][m].first == now){
                ve[d[now]][m].second=0;
                break;
            }
            else if(ve[d[now]][m].first > now) r=m-1;
            else l=m+1;
        }
        now=d[now];
    }
}
void update(){
    int j;
    for(int i=1; i<=n; i++){
        j=0;
        for(int k=0; k<edges[i].size(); k++){
            if(j<ve[i].size() && ve[i][j].first == edges[i][k].first){
                edges[i][k].second=ve[i][j].second;
                j++;
            }
            if(j == ve[i].size()) break;
        }
    }
}
void dijkstra(){
    vector<ll> dist(n+2, INF);
    vector<bool> vis(n+2, false);
    vector<int> pred(n+2, -1);
    priority_queue<pair<ll, int>, vector<pair<ll,int>>, greater<pair<ll,int>>> pq;

    dist[u]=0;
    pq.push({0, u});
    while(!pq.empty()){
        now=pq.top().second;
        pq.pop();
        if(!vis[now]){
            vis[now]=true;
            for(auto i: edges[now]){
                if(dist[i.first] >= dist[now] + i.second){
                    dist[i.first]=dist[now]+i.second;
                    pred[i.first]=now;
                    pq.push({dist[i.first], i.first});
                }
            }
        }
    }
    cout<<dist[v]<<"\n";
}
int main(){
    // ios_base::sync_with_stdio(false);
    // cin.tie(NULL);
    cin>>n>>m>>s>>t>>u>>v;
    for(int i=0; i<m; i++){
        cin>>a>>b>>c;
        edges[a].push_back({b, c});
        edges[b].push_back({a, c});
    }
    prim();
    bfs(s, t);
    update();
    dijkstra();
}

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

commuter_pass.cpp: In function 'void update()':
commuter_pass.cpp:92:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |         for(int k=0; k<edges[i].size(); k++){
      |                      ~^~~~~~~~~~~~~~~~
commuter_pass.cpp:93:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |             if(j<ve[i].size() && ve[i][j].first == edges[i][k].first){
      |                ~^~~~~~~~~~~~~
commuter_pass.cpp:97:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |             if(j == ve[i].size()) break;
      |                ~~^~~~~~~~~~~~~~~

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