Submission #574672

#	Time	Username	Problem	Language	Result	Execution time	Memory
574672		AJ00	Commuter Pass (JOI18_commuter_pass)	C++14	15 / 100	241 ms	28648 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;
#define int long long
int n;
const int MOD = 1000000007;
const int INF = 1e18;
pair<int,int> par[100001];
vector<pair<int,int>> adj[100001];
int dist[100001];
struct edges{
    int u,v,w;
    bool valid;
};
edges edge[200001];
void dijkstra(int s){
    priority_queue <pair<int,int>,vector<pair<int,int>>, greater<pair<int,int>>> pq;
    pq.push({0,s});
    memset(dist, 0x3f, sizeof dist);
    dist[s] = 0;
    par[s] = {-1,-1};
    while(!pq.empty()){
        pair<int,int> cur = pq.top();
        pq.pop();
        int p = cur.second;
        int d_p = cur.first;
        if (d_p != dist[p]){
            continue;
        }
        for (pair<int,int> child: adj[p]){
            if (dist[child.first] > dist[p] + edge[child.second].w){
                dist[child.first] = dist[p] + edge[child.second].w;
                par[child.first] = {p,child.second};
                pq.push({dist[child.first],child.first});
            }
        }
    }
}

signed main()
{
    //freopen("problemname.in", "r", stdin);
    //freopen("problemname.out", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int u,v,s,t,tc=1,q,k,m,c; 
    //cin >> tc;
    for (int poppo = 1; poppo <= tc; poppo++){
        //cout << "Case #" << poppo << ": "; 
        cin >> n >> m;
        cin >> s >> t;
        cin >> u >> v;
        for (int i = 0; i < m; i++){
            cin >> edge[i].u >> edge[i].v >> edge[i].w;
            edge[i].valid = false;
            adj[edge[i].u].push_back({edge[i].v,i});
            adj[edge[i].v].push_back({edge[i].u,i});
        }
        dijkstra(s);
        int rn = t;
        while (par[rn].first != -1){
            edge[par[rn].second].valid = true;
            rn = par[rn].first;
        }
        for (int i = 0; i < m; i++){
            if (edge[i].valid){
                edge[i].w = 0;
            }
        }
        dijkstra(u);
        cout << dist[v] << "\n";
    }
    return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:46:22: warning: unused variable 'q' [-Wunused-variable]
   46 |     int u,v,s,t,tc=1,q,k,m,c;
      |                      ^
commuter_pass.cpp:46:24: warning: unused variable 'k' [-Wunused-variable]
   46 |     int u,v,s,t,tc=1,q,k,m,c;
      |                        ^
commuter_pass.cpp:46:28: warning: unused variable 'c' [-Wunused-variable]
   46 |     int u,v,s,t,tc=1,q,k,m,c;
      |                            ^

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