Submission #833671

#	Time	Username	Problem	Language	Result	Execution time	Memory
833671		vjudge1	Commuter Pass (JOI18_commuter_pass)	C++17	0 / 100	2070 ms	18704 KiB

commuter_pass

#include<bits/stdc++.h>
using namespace std;
 
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define int long long
#define pb push_back
#define fi first
#define se second
#define mp make_pair
 
const int mod = LLONG_MAX;
const int maxn = 1e5 + 5;

int n, m, s, t, u, v;
vector<pair<int, int>> adj[maxn];
 
int32_t main()
{
    IOS
    cin >> n >> m;
    cin >> s >> t;
    cin >> u >> v;

    for(int i = 1; i <= m; i++){
        int a, b, c; cin >> a >> b >> c;
        adj[a].pb({b, c});
        adj[b].pb({a, c});
    }

    //pertama cari shortest path untuk dari s ke t
    //problem = bgmn kalau ada lbh dari 1 path dan jaraknya sama
    vector<int> d(n + 1, mod);
    vector<int> p(n + 1, -1);
    vector<int> vis(n + 1, 0);
    vector<int> jalan[n + 1];
    
    for(int i = 1; i <= n; i++){
        d[s] = 0;
        int v = -1;
        for(int j = 1; j <= n; j++){
            if(!vis[j] && (v == -1 || d[j] < d[v])){
                v = j;
            }
        }

        if(d[v] == mod) break;

        vis[v] = true;
        for(auto i : adj[v]){
            int to = i.fi;
            int val = i.se;

            if(d[v] + val < d[to]){
                d[to] = d[v] + val;
                p[to] = v;

                jalan[to].clear();
                jalan[to].pb(v);
            }else if(d[v] + val == d[to]){
                jalan[to].pb(v);
            }
        }
    }
    // for(auto j : jalan[t]){
    //     cout << j << " ";
    // }cout << endl;

    vector<int> path;
    map<pair<int, int>, bool> tanda;
    for(int i = t; i != s; i = p[i]){
        path.pb(i);
    }
    path.pb(s);
    reverse(path.begin(), path.end());
    
    for(int i = 1; i < path.size(); i++){
        tanda[{path[i], path[i - 1]}] = true;
        tanda[{path[i - 1], path[i]}] = true;
    }
    // for(auto i : tanda){
    //     cout << i << " ";
    // }cout << endl;

    vector<int> d1(n + 1, mod);
    vector<int> vis1(n + 1, 0);
    vector<int> p1(n + 1, -1);
    
    for(int i = 1; i <= n; i++){
        d1[u] = 0;
        int v = -1;
        for(int j = 1; j <= n; j++){
            if(!vis1[j] && (v == -1 || d1[j] < d1[v])){
                v = j;
            }
        }

        if(d1[v] == mod) break;

        vis1[v] = true;
        for(auto i : adj[v]){
            int to = i.fi;
            int val = i.se;

            if(tanda[{v, to}]){
                val = 0;
            }
            
            if(d1[v] + val < d1[to]){
                d1[to] = d1[v] + val;
                p[to] = v;
            }
        }
    }

    // vector<int> ans;
    // for(int i = v; i != u; i = p[i]){
    //     ans.pb(i);
    // }ans.pb(u);
    // reverse(ans.begin(), ans.end());
    // for(auto i : ans){
    //     cout << i << " ";
    // }cout << endl;
    cout << d1[v] << endl;
}

Compilation message (stderr)

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

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