oj.uz

답안 #491646

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
491646 2021-12-03T16:53:28 Z Carmel_Ab1 Commuter Pass (JOI18_commuter_pass) C++17
31 / 100
 706 ms 27400 KB 
#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

//using namespace __gnu_pbds;
using namespace std;

typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<pl> vpl;
typedef vector<ld> vld;
typedef pair<ld, ld> pld;
typedef vector<pi> vpi;

//typedef tree<ll, null_type, less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
template<typename T>
ostream &operator<<(ostream &os, vector<T> &a) {
    os << "[";
    for (int i = 0; i < ll(a.size()); i++) { os << a[i] << ((i != ll(a.size() - 1) ? " " : "")); }
    os << "]\n";
    return os;
}

#define all(x) x.begin(),x.end()
#define YES out("YES")
#define NO out("NO")
#define out(x){cout << x << "\n"; return;}
#define GLHF ios_base::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL)
#define print(x){for(auto ait:x) cout << ait << " "; cout << "\n";}
#define pb push_back
#define umap unordered_map

template<typename T1, typename T2>
istream &operator>>(istream &is, pair<T1, T2> &p) {
    is >> p.first >> p.second;
    return is;
}

template<typename T1, typename T2>
ostream &operator<<(ostream &os, pair<T1, T2> &p) {
    os << "" << p.first << " " << p.second << "";
    return os;
}

void usaco(string taskname) {
    string fin = taskname + ".in";
    string fout = taskname + ".out";
    const char *FIN = fin.c_str();
    const char *FOUT = fout.c_str();
    freopen(FIN, "r", stdin);
    freopen(FOUT, "w", stdout);
}

template<typename T>
void read(vector<T> &v) {
    int n = v.size();
    for (int i = 0; i < n; i++)
        cin >> v[i];
}

template<typename T>
vector<T> UNQ(vector<T> a) {
    vector<T> ans;
    for (T t: a)
        if (ans.empty() || t != ans.back())
            ans.push_back(t);
    return ans;
}

ll ceil(ll a, ll b) {
    ll ans = a / b;
    if (a % b)ans++;
    return ans;
}

ld log(ld a, ld b) { return log(b) / log(a); }

ll power(ll base, ll exp, ll M = 1e18) {//(base^exp)%M
    ll ans = 1;
    while (exp) {
        if (exp % 2 == 1)ans = ((ans % M) * (base % M)) % M;
        base = ((base % M) * (base % M)) % M;
        exp /= 2;
    }
    return ans;
}

string to_base(int n, int new_base) {
    string s;
    int nn = n;
    while (nn) {
        s += to_string(nn % new_base);
        nn /= new_base;
    }
    reverse(all(s));
    return s;
}

ll gcd(ll a, ll b) {
    if (a < b)swap(a, b);
    if (b == 0)return a;
    return gcd(b, a % b);
}

ll lcm(ll a, ll b) {
    ll x = (a / gcd(a, b));
    return b * x;
}

vl generate_array(ll n, ll mn = 1, ll mx = 1e18 + 1) {
    if (mx == 1e18 + 1)
        mx = n;
    vl ans(n);
    for (int i = 0; i < n; i++)
        ans[i] = (mn + rand() % (mx - mn + 1));
    return ans;
}

string substr(string s, int l, int r) {
    string ans;
    for (int i = l; i <= r; i++)
        ans += s[i];
    return ans;
}


void solve();

int main() {
    GLHF;
    int t = 1;
    //cin >> t;
    while (t--)
        solve();
}

vector<vpl>g;
vl dijkstra(int src){
    int n=g.size()-1;
    vl d(n+1,1e18);
    vector<bool>vis(n+1);

    priority_queue<vl,vvl,greater<vl>>pq;
    pq.push({0,src});

    while(pq.size()){
        vl v=pq.top();
        pq.pop();

        ll c=v[0],src=v[1];
        if(vis[src])
            continue;
        vis[src]=1;
        d[src]=min(d[src],c);
        for(pl nbr:g[src])
            if(!vis[nbr.first])
                pq.push({nbr.second+c,nbr.first});
    }
    return d;
}
void solve() {
    int n,m;
    cin >> n >> m;
    int s,t,u,v;
    cin >> s >> t >> u >> v;

    g.resize(n+1);
    for(int i=0; i<m; i++){
        ll u,v,w;
        cin >> u >> v >> w;
        g[u].pb({v,w});
        g[v].pb({u,w});
    }


    vl ds= dijkstra(s),dt= dijkstra(t),du= dijkstra(u),dv= dijkstra(v);
    ll ST=ds[t];

    vector<bool>ok(n+1);
    for(int i=1; i<=n;i ++)
        ok[i]=((ds[i]+dt[i])==ST);

    ll mnu=1e18,mnv=1e18;
    for(int i=1; i<=n; i++){
        if(!ok[i])
            continue;
        mnv=min(mnv,dv[i]);
        mnu=min(mnu,du[i]);
    }
    out(min(du[v],mnu+mnv))
}

Compilation message

commuter_pass.cpp: In function 'void usaco(std::string)':
commuter_pass.cpp:57:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |     freopen(FIN, "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~
commuter_pass.cpp:58:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |     freopen(FOUT, "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 699 ms 23812 KB Output is correct
2 Correct 582 ms 25788 KB Output is correct
3 Correct 706 ms 25512 KB Output is correct
4 Correct 675 ms 26172 KB Output is correct
5 Correct 546 ms 24808 KB Output is correct
6 Correct 665 ms 27400 KB Output is correct
7 Correct 589 ms 25764 KB Output is correct
8 Correct 524 ms 24916 KB Output is correct
9 Correct 648 ms 26496 KB Output is correct
10 Correct 648 ms 27060 KB Output is correct
11 Correct 117 ms 13076 KB Output is correct
12 Correct 658 ms 26420 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 606 ms 22176 KB Output is correct
2 Correct 499 ms 25196 KB Output is correct
3 Correct 551 ms 25188 KB Output is correct
4 Correct 485 ms 24148 KB Output is correct
5 Correct 577 ms 24928 KB Output is correct
6 Correct 547 ms 25584 KB Output is correct
7 Correct 488 ms 25084 KB Output is correct
8 Correct 490 ms 24976 KB Output is correct
9 Correct 547 ms 25192 KB Output is correct
10 Correct 568 ms 24756 KB Output is correct
11 Correct 120 ms 13132 KB Output is correct
12 Correct 503 ms 25012 KB Output is correct

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 2464 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Incorrect 2 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 699 ms 23812 KB Output is correct
2 Correct 582 ms 25788 KB Output is correct
3 Correct 706 ms 25512 KB Output is correct
4 Correct 675 ms 26172 KB Output is correct
5 Correct 546 ms 24808 KB Output is correct
6 Correct 665 ms 27400 KB Output is correct
7 Correct 589 ms 25764 KB Output is correct
8 Correct 524 ms 24916 KB Output is correct
9 Correct 648 ms 26496 KB Output is correct
10 Correct 648 ms 27060 KB Output is correct
11 Correct 117 ms 13076 KB Output is correct
12 Correct 658 ms 26420 KB Output is correct
13 Correct 606 ms 22176 KB Output is correct
14 Correct 499 ms 25196 KB Output is correct
15 Correct 551 ms 25188 KB Output is correct
16 Correct 485 ms 24148 KB Output is correct
17 Correct 577 ms 24928 KB Output is correct
18 Correct 547 ms 25584 KB Output is correct
19 Correct 488 ms 25084 KB Output is correct
20 Correct 490 ms 24976 KB Output is correct
21 Correct 547 ms 25192 KB Output is correct
22 Correct 568 ms 24756 KB Output is correct
23 Correct 120 ms 13132 KB Output is correct
24 Correct 503 ms 25012 KB Output is correct
25 Correct 36 ms 2464 KB Output is correct
26 Correct 1 ms 332 KB Output is correct
27 Incorrect 2 ms 332 KB Output isn't correct
28 Halted 0 ms 0 KB -