oj.uz

Submission #574672

# Submission time Handle Problem Language Result Execution time Memory
574672 2022-06-09T07:42:13 Z AJ00 Commuter Pass (JOI18_commuter_pass) C++14
15 / 100
 241 ms 28648 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 28648 KB Output is correct
2 Correct 217 ms 27200 KB Output is correct
3 Correct 223 ms 27268 KB Output is correct
4 Incorrect 203 ms 27412 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 28472 KB Output is correct
2 Correct 230 ms 27096 KB Output is correct
3 Correct 229 ms 28140 KB Output is correct
4 Correct 235 ms 27056 KB Output is correct
5 Correct 239 ms 27128 KB Output is correct
6 Correct 238 ms 27296 KB Output is correct
7 Correct 240 ms 28084 KB Output is correct
8 Correct 241 ms 27168 KB Output is correct
9 Correct 233 ms 28172 KB Output is correct
10 Correct 228 ms 27072 KB Output is correct
11 Correct 106 ms 15404 KB Output is correct
12 Correct 226 ms 27352 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 5904 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 28648 KB Output is correct
2 Correct 217 ms 27200 KB Output is correct
3 Correct 223 ms 27268 KB Output is correct
4 Incorrect 203 ms 27412 KB Output isn't correct
5 Halted 0 ms 0 KB -