oj.uz

답안 #862162

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
862162 2023-10-17T15:03:55 Z efedmrlr Commuter Pass (JOI18_commuter_pass) C++17
100 / 100
 721 ms 65516 KB 
#include <bits/stdc++.h>

using namespace std;

#define n_l '\n'
#define dbg(...) cout << "[" << #__VA_ARGS__ << "]: "; cout << to_string(__VA_ARGS__) << endl
template <typename T, size_t N> int SIZE(const T (&t)[N]){ return N; } template<typename T> int SIZE(const T &t){ return t.size(); } string to_string(const string s, int x1=0, int x2=1e9){ return '"' + ((x1 < s.size()) ? s.substr(x1, x2-x1+1) : "") + '"'; } string to_string(const char* s) { return to_string((string) s); } string to_string(const bool b) { return (b ? "true" : "false"); } string to_string(const char c){ return string({c}); } template<size_t N> string to_string(const bitset<N> &b, int x1=0, int x2=1e9){ string t = ""; for(int __iii__ = min(x1,SIZE(b)),  __jjj__ = min(x2, SIZE(b)-1); __iii__ <= __jjj__; ++__iii__){ t += b[__iii__] + '0'; } return '"' + t + '"'; } template <typename A, typename... C> string to_string(const A (&v), int x1=0, int x2=1e9, C... coords); int l_v_l_v_l = 0, t_a_b_s = 0; template <typename A, typename B> string to_string(const pair<A, B> &p) { l_v_l_v_l++; string res = "(" + to_string(p.first) + ", " + to_string(p.second) + ")"; l_v_l_v_l--; return res; } template <typename A, typename... C> string to_string(const A (&v), int x1, int x2, C... coords) { int rnk = rank<A>::value; string tab(t_a_b_s, ' '); string res = ""; bool first = true; if(l_v_l_v_l == 0) res += n_l; res += tab + "["; x1 = min(x1, SIZE(v)), x2 = min(x2, SIZE(v)); auto l = begin(v); advance(l, x1); auto r = l; advance(r, (x2-x1) + (x2 < SIZE(v))); for (auto e = l; e != r; e = next(e)) { if (!first) { res += ", "; } first = false; l_v_l_v_l++; if(e != l){ if(rnk > 1) { res += n_l; t_a_b_s = l_v_l_v_l; }; } else{ t_a_b_s = 0; } res += to_string(*e, coords...); l_v_l_v_l--; } res += "]"; if(l_v_l_v_l == 0) res += n_l; return res; } void dbgm(){;} template<typename Heads, typename... Tails> void dbgm(Heads H, Tails... T){ cout << to_string(H) << " | "; dbgm(T...); } 
#define dbgm(...) cout << "[" << #__VA_ARGS__ << "]: "; dbgm(__VA_ARGS__); cout << endl


#define int long long int
#define MP make_pair
#define pb push_back
#define REP(i,n) for(int (i) = 0; (i) < (n); (i)++)

void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}


const double EPS = 0.00001;
const int INF = 1e9+500;
const int N = 3e5+5;
const int ALPH = 26;
const int LGN = 25;
const int MOD = 1e9+7;
int n,m,q;
int s,t,u,v;
vector<array<int,2> > adj[N];
vector<vector<int> > sadj(N);
vector<vector<int> > tmpadj;
vector<int> vis(N, 0);
void dijkstra(vector<int> &spath, int sour) {
    priority_queue<array<int,3> , vector<array<int,3> > , greater<array<int,3> > > que; //length, target, source
    que.push({0, sour, 0});
    while(que.size()) {
        auto cur = que.top();
        que.pop();
        if(spath[cur[1]] != INF) {
            if(spath[cur[1]] == cur[0]) {
                sadj[cur[1]].pb(cur[2]);
            }
            continue;
        }
        spath[cur[1]] = cur[0];
        sadj[cur[1]].pb(cur[2]);
        for(auto c : adj[cur[1]]) {
            que.push({cur[0] + c[1], c[0], cur[1]});
        }
    }

}
void dijkstra2(vector<array<int,2> > &spath, int sour) {
   priority_queue<array<int,3> , vector<array<int,3> > , greater<array<int,3> > > que; //length, target, powerup
  
   que.push({0, sour, 0});
   while(que.size()) {
        auto cur = que.top();
        que.pop();
        if(spath[cur[1]][cur[2]] != INF) {
            continue;
        }

        spath[cur[1]][cur[2]] = cur[0];
        if(!cur[2] && !vis[cur[1]]) {
            queue<int> bfs;
            bfs.push(cur[1]);
            while(bfs.size()) {
                int el = bfs.front();
                bfs.pop();
                vis[el] = 1;
                que.push({cur[0], el, 1});
                for(auto c : sadj[el]) {
                    if(vis[c]) continue;
                    bfs.push(c);
                }
            }
        }
        for(auto c : adj[cur[1]]) {
            que.push({cur[0] + c[1], c[0], cur[2]});
        }
   }
}
void dfs(int node) {
    vis[node] = 1;
    for(auto c : sadj[node]) {
        tmpadj[node].pb(c);
        if(vis[c]) continue;
        dfs(c);
    }
}

inline void solve() {
    cin>>n>>m;
    cin>>s>>t;
    cin>>u>>v;
    for(int i = 0; i<m; i++) {
        int a,b,c;
        cin>>a>>b>>c;
        adj[a].pb({b,c});
        adj[b].pb({a,c});
    }

    vector<int> spath(n+1, INF);
    dijkstra(spath, s);

    tmpadj.assign(n+1, vector<int>());
    dfs(t);
    vis.assign(n+2, 0);
    swap(tmpadj, sadj);

    vector<array<int ,2> > spat(n+1, {INF,INF});
    dijkstra2(spat, u);

    int ans = min(spat[v][0], spat[v][1]);
    spat.assign(n+1, {INF, INF});
    vis.assign(n+1, 0);

    dijkstra2(spat, v);
    ans = min(ans, min(spat[u][0], spat[u][1]));
    cout<<ans<<"\n";

}
 
signed main() {
    //freopen("milkvisits.in", "r", stdin);
    //freopen("milkvisits.out", "w", stdout);
    fastio();
    int test = 1;
    //cin>>test;
    while(test--) {
        solve();
    }
    
}

Compilation message

commuter_pass.cpp: In function 'std::string to_string(std::string, int, int)':
commuter_pass.cpp:7:208: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | template <typename T, size_t N> int SIZE(const T (&t)[N]){ return N; } template<typename T> int SIZE(const T &t){ return t.size(); } string to_string(const string s, int x1=0, int x2=1e9){ return '"' + ((x1 < s.size()) ? s.substr(x1, x2-x1+1) : "") + '"'; } string to_string(const char* s) { return to_string((string) s); } string to_string(const bool b) { return (b ? "true" : "false"); } string to_string(const char c){ return string({c}); } template<size_t N> string to_string(const bitset<N> &b, int x1=0, int x2=1e9){ string t = ""; for(int __iii__ = min(x1,SIZE(b)),  __jjj__ = min(x2, SIZE(b)-1); __iii__ <= __jjj__; ++__iii__){ t += b[__iii__] + '0'; } return '"' + t + '"'; } template <typename A, typename... C> string to_string(const A (&v), int x1=0, int x2=1e9, C... coords); int l_v_l_v_l = 0, t_a_b_s = 0; template <typename A, typename B> string to_string(const pair<A, B> &p) { l_v_l_v_l++; string res = "(" + to_string(p.first) + ", " + to_string(p.second) + ")"; l_v_l_v_l--; return res; } template <typename A, typename... C> string to_string(const A (&v), int x1, int x2, C... coords) { int rnk = rank<A>::value; string tab(t_a_b_s, ' '); string res = ""; bool first = true; if(l_v_l_v_l == 0) res += n_l; res += tab + "["; x1 = min(x1, SIZE(v)), x2 = min(x2, SIZE(v)); auto l = begin(v); advance(l, x1); auto r = l; advance(r, (x2-x1) + (x2 < SIZE(v))); for (auto e = l; e != r; e = next(e)) { if (!first) { res += ", "; } first = false; l_v_l_v_l++; if(e != l){ if(rnk > 1) { res += n_l; t_a_b_s = l_v_l_v_l; }; } else{ t_a_b_s = 0; } res += to_string(*e, coords...); l_v_l_v_l--; } res += "]"; if(l_v_l_v_l == 0) res += n_l; return res; } void dbgm(){;} template<typename Heads, typename... Tails> void dbgm(Heads H, Tails... T){ cout << to_string(H) << " | "; dbgm(T...); }
      |                                                                                                                                                                                                             ~~~^~~~~~~~~~

Subtask #1
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 708 ms 60620 KB Output is correct
2 Correct 588 ms 57972 KB Output is correct
3 Correct 615 ms 65052 KB Output is correct
4 Correct 690 ms 58996 KB Output is correct
5 Correct 619 ms 60012 KB Output is correct
6 Correct 712 ms 60616 KB Output is correct
7 Correct 617 ms 61556 KB Output is correct
8 Correct 561 ms 59708 KB Output is correct
9 Correct 721 ms 60756 KB Output is correct
10 Correct 649 ms 60012 KB Output is correct
11 Correct 128 ms 36176 KB Output is correct
12 Correct 642 ms 59588 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 697 ms 62472 KB Output is correct
2 Correct 638 ms 53532 KB Output is correct
3 Correct 598 ms 59128 KB Output is correct
4 Correct 549 ms 53120 KB Output is correct
5 Correct 546 ms 54380 KB Output is correct
6 Correct 534 ms 62956 KB Output is correct
7 Correct 577 ms 65268 KB Output is correct
8 Correct 560 ms 61264 KB Output is correct
9 Correct 556 ms 61312 KB Output is correct
10 Correct 517 ms 52432 KB Output is correct
11 Correct 149 ms 38584 KB Output is correct
12 Correct 532 ms 65516 KB Output is correct

Subtask #3
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 49 ms 21340 KB Output is correct
2 Correct 6 ms 16984 KB Output is correct
3 Correct 5 ms 16984 KB Output is correct
4 Correct 92 ms 26576 KB Output is correct
5 Correct 49 ms 23168 KB Output is correct
6 Correct 7 ms 17204 KB Output is correct
7 Correct 8 ms 17296 KB Output is correct
8 Correct 10 ms 17460 KB Output is correct
9 Correct 7 ms 17176 KB Output is correct
10 Correct 46 ms 23256 KB Output is correct
11 Correct 5 ms 16732 KB Output is correct
12 Correct 5 ms 16732 KB Output is correct
13 Correct 5 ms 16988 KB Output is correct
14 Correct 6 ms 16988 KB Output is correct
15 Correct 6 ms 16992 KB Output is correct

Subtask #4
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 708 ms 60620 KB Output is correct
2 Correct 588 ms 57972 KB Output is correct
3 Correct 615 ms 65052 KB Output is correct
4 Correct 690 ms 58996 KB Output is correct
5 Correct 619 ms 60012 KB Output is correct
6 Correct 712 ms 60616 KB Output is correct
7 Correct 617 ms 61556 KB Output is correct
8 Correct 561 ms 59708 KB Output is correct
9 Correct 721 ms 60756 KB Output is correct
10 Correct 649 ms 60012 KB Output is correct
11 Correct 128 ms 36176 KB Output is correct
12 Correct 642 ms 59588 KB Output is correct
13 Correct 697 ms 62472 KB Output is correct
14 Correct 638 ms 53532 KB Output is correct
15 Correct 598 ms 59128 KB Output is correct
16 Correct 549 ms 53120 KB Output is correct
17 Correct 546 ms 54380 KB Output is correct
18 Correct 534 ms 62956 KB Output is correct
19 Correct 577 ms 65268 KB Output is correct
20 Correct 560 ms 61264 KB Output is correct
21 Correct 556 ms 61312 KB Output is correct
22 Correct 517 ms 52432 KB Output is correct
23 Correct 149 ms 38584 KB Output is correct
24 Correct 532 ms 65516 KB Output is correct
25 Correct 49 ms 21340 KB Output is correct
26 Correct 6 ms 16984 KB Output is correct
27 Correct 5 ms 16984 KB Output is correct
28 Correct 92 ms 26576 KB Output is correct
29 Correct 49 ms 23168 KB Output is correct
30 Correct 7 ms 17204 KB Output is correct
31 Correct 8 ms 17296 KB Output is correct
32 Correct 10 ms 17460 KB Output is correct
33 Correct 7 ms 17176 KB Output is correct
34 Correct 46 ms 23256 KB Output is correct
35 Correct 5 ms 16732 KB Output is correct
36 Correct 5 ms 16732 KB Output is correct
37 Correct 5 ms 16988 KB Output is correct
38 Correct 6 ms 16988 KB Output is correct
39 Correct 6 ms 16992 KB Output is correct
40 Correct 626 ms 60316 KB Output is correct
41 Correct 616 ms 61156 KB Output is correct
42 Correct 580 ms 59404 KB Output is correct
43 Correct 168 ms 39464 KB Output is correct
44 Correct 188 ms 40340 KB Output is correct
45 Correct 578 ms 53772 KB Output is correct
46 Correct 569 ms 55092 KB Output is correct
47 Correct 578 ms 50300 KB Output is correct
48 Correct 204 ms 40436 KB Output is correct
49 Correct 600 ms 57940 KB Output is correct
50 Correct 593 ms 52436 KB Output is correct
51 Correct 546 ms 53324 KB Output is correct