Submission #833469

#	Time	Username	Problem	Language	Result	Execution time	Memory
833469		vjudge1	Commuter Pass (JOI18_commuter_pass)	C++17	15 / 100	560 ms	40076 KiB

commuter_pass

#include <bits/stdc++.h>
#define int long long
#define vi vector<int>
#define endl "\n"
#define invec(name, n) for(int abc = 0; abc < n; abc++) cin >> name[abc];
#define outvec(name, n) for(int abc = 0; abc < n; abc++) cout << name[abc] << " ";
#define format_decimal(x) fixed << setprecision(x)

using namespace std;

const int INF = numeric_limits<int>::max();

vector<int> cost;
map<pair<int, int>, int> meps;

// Represents an edge between two nodes
struct Edge {
    int to;
    int weight;
};

// Dijkstra's algorithm to find the shortest path
void dijkstra(const vector<vector<Edge>>& graph, int source, int target, vector<int>& distance, unordered_map<int, int>& parent) {
    int n = graph.size();
    distance.assign(n, INF);
    parent.clear();
    
    distance[source] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, source});
    
    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();
        
        for (const Edge& edge : graph[u]) {
            int v = edge.to;
            int weight = cost[edge.weight];
            
            if (distance[u] + weight < distance[v]) {
                distance[v] = distance[u] + weight;
                parent[v] = u;
                pq.push({distance[v], v});
            }
        }
    }
}

// Reconstructs the path from source to target
vector<int> reconstructPath(const unordered_map<int, int>& parent, int target) {
    vector<int> path;
    while (parent.find(target) != parent.end()) {
        path.push_back(target);
        target = parent.at(target);
    }
    path.push_back(target);
    reverse(path.begin(), path.end());
    return path;
}

signed main() {
    int n, m; // Number of nodes and edges
    cin >> n >> m;
    
    int s, t; cin >> s >> t;
    s--, t--;
    int x, y; cin >> x >> y;
    x--, y--;
    
    cost.assign(m, 0);
    vector<vector<Edge>> graph(n);
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        cost[i] = w;
        u--, v--;
        meps[{u, v}] = i;
        graph[u].push_back({v, i});
        graph[v].push_back({u, i}); // Undirected graph
    }
    
    vector<int> distance, dist;
    unordered_map<int, int> parent, par;
    dijkstra(graph, s, t, distance, parent);

	vector<int> path = reconstructPath(parent, t);
    for(int i = 0; i < path.size()-1; i++)
    {
    	int a = min(path[i], path[i+1]);
    	int b = max(path[i], path[i+1]);
    	cost[meps[{a, b}]] = 0;
	}
    
    dijkstra(graph, x, y, dist, par);
    cout << dist[y] << endl;
    
    return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:87:22: 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]
   87 |     for(int i = 0; i < path.size()-1; i++)
      |                    ~~^~~~~~~~~~~~~~~

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