Submission #1087589

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087589		shiori_chan	Commuter Pass (JOI18_commuter_pass)	C++14	15 / 100	2073 ms	262144 KiB

commuter_pass

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#define int long long
using namespace std;
const int nd = 1e5 + 1 , INF = 1e18;
vector<pair<int,int> > adj[nd];
vector<int> dis[4] , g[nd] , in(nd , 0) , topo , f(nd , INF) , par[nd];
priority_queue< pair<int , int> , vector< pair<int,int> > , greater< pair<int,int> > >q;
bool vs[nd];
int mn = INF;
void dijs(int r , int p){
    q.push({0 , r});
    dis[p][r] = 0;
    memset(vs , false , nd);
    while(!q.empty()){
        int u = q.top().second , h = q.top().first; 
        q.pop();
        if(vs[u])continue;
        //cout << r << " " << h << " " << u <<" " << '\n';
        
        vs[u] = true;
        for(auto v : adj[u])if(!vs[v.first]){
            //cout << v.first << '\n';
            if(h + v.second < dis[p][v.first]){
                dis[p][v.first] = h + v.second , q.push({dis[p][v.first] , v.first});
            }
        }
    }
}

void build(int u){
    for(auto [v, vw] : adj[u]){
        if(dis[0][u] == dis[0][v] + vw){
            g[v].push_back(u);
            par[u].push_back(v);
            ++ in[u];
            build(v);
        }
    }
}

void bfs(int s){
    queue<int> h;
    h.push(s);
    while(!h.empty()){
        int u = h.front();
        h.pop();

        topo.push_back(u);
        for(int v : g[u]){
            --in[v];
            if(!in[v])h.push(v);
        }
    }

}
void solve(){
    int n,m;
    int s ,t , x, y;
    cin >> n >> m;

    cin >> s >> t >> x >> y;
    for(int i = 0;i < 4; ++i)dis[i].resize(nd , INF);
    
    for(int i = 1;i <= m; ++i){
        int l , r ,w;
        cin >> l >> r >> w;
        adj[l].push_back({r , w}) , adj[r].push_back({l , w});
    }
    dijs(s , 0) , dijs(t , 1) , dijs(x , 2) , dijs(y , 3);
    int mn = dis[0][t];

    memset(vs , false , sizeof(vs));
    build(t);bfs(s);
    //for(int i = 1;i <= n; ++i)cout << in[i] << '\n';

    f[s] = dis[2][s];
    int res = INF;

    for(int i = 1;i < topo.size(); ++i){
        int u = topo[i];
        f[u] = dis[2][u];
        for(auto v : par[u]){
            f[u] = min(f[u] , f[v]);
        }
        res = min(res , f[u] + dis[3][u]);
    }

    f[s] = dis[3][s];
    res = min(res ,f[s] + dis[2][s]);

    for(int i = 1;i < topo.size(); ++i){
        int u = topo[i];
        f[u] = dis[3][u];
        for(auto v : par[u]){
            f[u] = min(f[u] , f[v]);
        }
        res = min(res , f[u] + dis[2][u]);
    }

    res = min(res , dis[2][y]);
    cout << res;
}

signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);
    solve();
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void build(long long int)':
commuter_pass.cpp:34:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   34 |     for(auto [v, vw] : adj[u]){
      |              ^
commuter_pass.cpp: In function 'void solve()':
commuter_pass.cpp:82:21: 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]
   82 |     for(int i = 1;i < topo.size(); ++i){
      |                   ~~^~~~~~~~~~~~~
commuter_pass.cpp:94:21: 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]
   94 |     for(int i = 1;i < topo.size(); ++i){
      |                   ~~^~~~~~~~~~~~~
commuter_pass.cpp:73:9: warning: unused variable 'mn' [-Wunused-variable]
   73 |     int mn = dis[0][t];
      |         ^~

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