oj.uz

Submission #796465

# Submission time Handle Problem Language Result Execution time Memory
796465 2023-07-28T12:11:21 Z mindiyak Commuter Pass (JOI18_commuter_pass) C++17
0 / 100
 91 ms 111680 KB 
#pragma GCC optimize("O3")
#pragma GCC target("sse4")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ld, ld> pd;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<vector<int>> vvi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
#define FOR(i, a, b) for (ll i = a; i < (b); i++)
#define F0R(i, a) for (ll i = 0; i < (a); i++)
#define FORd(i, a, b) for (ll i = (b)-1; i >= a; i--)
#define F0Rd(i, a) for (ll i = (a)-1; i >= 0; i--)
#define trav(a, x) for (auto &a : x)
#define uid(a, b) uniform_int_distribution<int>(a, b)(rng)
#define len(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define fst first
#define nl endl
#define sec second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define ins insert
const int MOD = 1000000007;
const int MX = INT_MAX;
const int MN = INT_MIN;
void init()
{
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
#endif
}
void fastIO()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
}

vi path;
vector<vector<pair<int,ll>>> edges(1e6);
ll cost = 0;
ll cost2 = 0;

void spfa(int start,int end,int type){
    queue<int> arr;
    vector<ll> cost_list(1e6,1e15);
    vector<vi> pos_path(1e6);
    cost_list[start] = 0;
    arr.push(start);
    while(arr.size() > 0){
        int data = arr.front();arr.pop();
        FOR(i,0,edges[data].size()){
            pair<int,ll> node = edges[data][i];
            if(cost_list[node.first] > cost_list[data]+node.second){
                arr.push(node.first);
                pos_path[node.first] = pos_path[data];
                pos_path[node.first].push_back(data);
                cost_list[node.first] = cost_list[data]+node.second;
            }
        }
    }
    if(type == 0){
        path = pos_path[end];
        return;
    }if(type == 1)cost2 = cost_list[end];
    ll MI = 1e15;
    
    FOR(i,0,path.size()){
        MI = min(MI,cost_list[path[i]]);
        if(MI == 0)return;
    }
    cost += MI;
}

void solve()
{
    int n,m;cin>>n>>m;
    int p,q;cin >> p >> q;
    int s,t;cin >> s >> t;

    FOR(i,0,m){
        int a,b;ll c;cin >> a >> b >> c;
        edges[a].pb({b,c});
        edges[b].pb({a,c});
    }

    spfa(p,q,0);
    path.pb(q);

    // FOR(i,0,path.size())cout << path[i] << " ";
    // cout << endl;

    spfa(s,t,1);

    spfa(t,-1,2);

    // cout << cost << endl;

    // cout << cost2 << endl;

    if(cost2 < cost){
        cout << cost2 << endl;
        return;
    }
    cout << cost << endl;
}


int main()
{
    fastIO();
    init();
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
    return 0;
}

Compilation message

commuter_pass.cpp: In function 'void spfa(int, int, int)':
commuter_pass.cpp:17:39: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 | #define FOR(i, a, b) for (ll i = a; i < (b); i++)
      |                                       ^
commuter_pass.cpp:63:9: note: in expansion of macro 'FOR'
   63 |         FOR(i,0,edges[data].size()){
      |         ^~~
commuter_pass.cpp:17:39: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 | #define FOR(i, a, b) for (ll i = a; i < (b); i++)
      |                                       ^
commuter_pass.cpp:79:5: note: in expansion of macro 'FOR'
   79 |     FOR(i,0,path.size()){
      |     ^~~
commuter_pass.cpp: In function 'void init()':
commuter_pass.cpp:40:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |     freopen("input.in", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:41:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |     freopen("output.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 91 ms 111680 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 83 ms 111600 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 87 ms 111604 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Runtime error 91 ms 111680 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -