Submission #1087605

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087605		shiori_chan	Commuter Pass (JOI18_commuter_pass)	C++17	15 / 100	2069 ms	262144 KiB

commuter_pass

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#define int long long
using namespace std;
const int nd = 1e5 + 5 , INF = 1e15;
vector<pair<int,int> > adj[nd];
vector<int>g[nd + 4] , in(nd + 5 , 0) , topo , f(nd + 4) , par[nd + 4];
priority_queue< pair<int , int> , vector< pair<int,int> > , greater< pair<int,int> > >q;
bool vs[nd + 4];
vector< vector<int> > dis(5 , vector<int> (nd + 1 , 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 = 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);

    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);
    #define task "task"
    //freopen(task".inp","r",stdin);freopen(task".out","w",stdout);
    solve();
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void solve()':
commuter_pass.cpp:80: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]
   80 |     for(int i = 1;i < topo.size(); ++i){
      |                   ~~^~~~~~~~~~~~~
commuter_pass.cpp:92: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]
   92 |     for(int i = 1;i < topo.size(); ++i){
      |                   ~~^~~~~~~~~~~~~

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