Submission #1246382

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246382		nlsosad	Commuter Pass (JOI18_commuter_pass)	C++20	Compilation error	0 ms	0 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll LINF = (ll)4e18;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;
    int S, T; 
    cin >> S >> T;
    int U, V; 
    cin >> U >> V;

    struct Edge{int to; ll w;};
    vector<vector<Edge>> adj(N+1);
    for(int i=0;i<M;i++){
        int u,v; ll w;
        cin >> u >> v >> w;
        adj[u].push_back({v,w});
        adj[v].push_back({u,w});
    }

    auto dijkstra = [&](int src){
        vector<ll> dist(N+1, LINF);
        priority_queue<pair<ll,int>, vector<...>, greater<...>> pq;
        dist[src] = 0;
        pq.push({0, src});
        while(!pq.empty()){
            auto [d,u] = pq.top(); pq.pop();
            if(d > dist[u]) continue;
            for(auto &e : adj[u]){
                int v = e.to; ll w = e.w;
                if(dist[v] > d + w){
                    dist[v] = d + w;
                    pq.push({dist[v], v});
                }
            }
        }
        return dist;
    };

    auto d_s = dijkstra(S);
    auto d_u = dijkstra(U);
    auto d_v = dijkstra(V);

    // Xây DAG của tất cả cạnh (u->v) thỏa d_s[u]+w = d_s[v]
    vector<vector<int>> dag(N+1);
    vector<int> indeg(N+1, 0);
    for(int u=1;u<=N;u++){
        for(auto &e : adj[u]){
            int v = e.to; ll w = e.w;
            if(d_s[u] + w == d_s[v]){
                dag[u].push_back(v);
                indeg[v]++;
            }
        }
    }

    // Topo-sort
    queue<int> q;
    for(int i=1;i<=N;i++) 
        if(indeg[i]==0) q.push(i);

    vector<int> ord;
    while(!q.empty()){
        int u = q.front(); q.pop();
        ord.push_back(u);
        for(int v: dag[u]){
            if(--indeg[v]==0) 
                q.push(v);
        }
    }

    // DP tìm answer
    vector<ll> best_u(N+1, LINF);
    ll answer = d_u[V];  // trường hợp không dùng vé tháng
    for(int v: ord){
        best_u[v] = min(best_u[v], d_u[v]);
        answer = min(answer, best_u[v] + d_v[v]);
        for(int w: dag[v]){
            best_u[w] = min(best_u[w], best_u[v]);
        }
    }

    cout << answer << "\n";
    return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In lambda function:
commuter_pass.cpp:28:45: error: expected parameter pack before '...'
   28 |         priority_queue<pair<ll,int>, vector<...>, greater<...>> pq;
      |                                             ^~~
commuter_pass.cpp:28:48: error: template argument 1 is invalid
   28 |         priority_queue<pair<ll,int>, vector<...>, greater<...>> pq;
      |                                                ^
commuter_pass.cpp:28:48: error: template argument 2 is invalid
commuter_pass.cpp:28:59: error: expected parameter pack before '...'
   28 |         priority_queue<pair<ll,int>, vector<...>, greater<...>> pq;
      |                                                           ^~~
commuter_pass.cpp:28:59: error: template argument 1 is invalid
commuter_pass.cpp:28:62: error: template argument 2 is invalid
   28 |         priority_queue<pair<ll,int>, vector<...>, greater<...>> pq;
      |                                                              ^~
commuter_pass.cpp:28:62: error: template argument 3 is invalid
commuter_pass.cpp:30:12: error: request for member 'push' in 'pq', which is of non-class type 'int'
   30 |         pq.push({0, src});
      |            ^~~~
commuter_pass.cpp:31:19: error: request for member 'empty' in 'pq', which is of non-class type 'int'
   31 |         while(!pq.empty()){
      |                   ^~~~~
commuter_pass.cpp:32:29: error: request for member 'top' in 'pq', which is of non-class type 'int'
   32 |             auto [d,u] = pq.top(); pq.pop();
      |                             ^~~
commuter_pass.cpp:32:39: error: request for member 'pop' in 'pq', which is of non-class type 'int'
   32 |             auto [d,u] = pq.top(); pq.pop();
      |                                       ^~~
commuter_pass.cpp:38:24: error: request for member 'push' in 'pq', which is of non-class type 'int'
   38 |                     pq.push({dist[v], v});
      |                        ^~~~