oj.uz

답안 #646168

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
646168 2022-09-28T21:08:54 Z swagchicken Robot (JOI21_ho_t4) C++14
100 / 100
 884 ms 85212 KB 
/*
 ID: swagchicken1
 PROG:
 LANG: C++11
 */
 
#include <iostream>
#include <tuple>
#include <cmath>
#include <string>
#include <cstring>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <algorithm>
#include <vector>
#include <fstream>
#include <iomanip>
#include <ctime>
#include <cctype>
#include <climits>
#include <chrono>
#include <numeric>
#include <functional>
 
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef vector< vector <int> > vvi;
typedef pair<int, int> pii;
typedef pair < pair < int, int >, int > piii;
typedef pair < pair <int, int > , pair <int, int> > piiii;
typedef pair<ll, ll> pll;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
 
#define FOR(i,a,b) for(int i = a; i < b; i ++)
#define RFOR(i,a,b) for(int i = a-1; i >= b; i --)
#define all(a) a.begin(), a.end()
#define endl '\n';
#define sz(x) (int)(x).size()
 
#define mp make_pair
#define pb push_back
#define ff first
#define ss second
 
template <typename T>
void pr(vector<T> &v) {
    FOR(i, 0, sz(v)) cout << v[i] << " ";
    cout << endl;
}
template <typename T>
void pr(vector<vector<T> > &v) {
    FOR(i, 0, sz(v)) { pr(v[i]); }
}
template <typename T>
void re(T &x) {
    cin >> x;
}
template <typename T>
void re(vector<T> &a) {
    FOR(i, 0, sz(a)) re(a[i]);
}
template <class Arg, class... Args>
void re(Arg &first, Args &... rest) {
    re(first);
    re(rest...);
}
template <typename T>
void pr(T x) {
    cout << x << endl;
}
template <class Arg, class... Args>
void pr(const Arg &first, const Args &... rest) {
    cout << first << " ";
    pr(rest...);
    cout << endl;
}
void ps() { cout << endl; }
template<class T, class... Ts>
void ps(const T& t, const Ts&... ts) {
    cout << t; if (sizeof...(ts)) cout << " "; ps(ts...);
}
 
const ll MOD  = 1000000007;
#define inf 1e18;
#define INF INT_MAX
//#define DEBUG
 
long double PI = 4*atan(1);
long double eps = 1e-9;

struct edge {
    int nxt;
    int col;
    ll w;
};
vector<map<int, vector<edge>>> adj;
map<int, ll> sumw[100010] = {};

ll dp[100010] = {};
map<int, ll> dp2[100010] = {};


int main() {
    //auto start = chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);cin.tie(0);
    //ofstream cout("output.txt");
    //ifstream cin("input.txt");
    #ifdef DEBUG
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
        // freopen("cowmbat.in", "r", stdin);
        // freopen("cowmbat.out", "w", stdout);
    #endif

    int n,m; cin >> n >> m;
    adj.resize(n);
    FOR(i,0,m) {
        int u,v; cin >> u >> v; u--; v--;
        int c; ll p; cin >> c >> p;
        adj[u][c].pb({v, c, p});
        adj[v][c].pb({u, c, p});
        sumw[u][c] += p;
        sumw[v][c] += p;
    }

    FOR(i,0,n) {
        dp[i] = 1e18;
    }

    priority_queue<pair<ll, pii>, vector<pair<ll, pii>>, greater<pair<ll, pii>>> pq;
    dp[0] = 0;
    pq.push({0, {0, 0}});
    while(!pq.empty()) {
        
        pair<ll, pii> curr = pq.top(); pq.pop();
        ll d = curr.ff;
        int node = curr.ss.ff;
        int c = curr.ss.ss;
        if(c > 0) {
            if(d != dp2[node][c]) continue;
            for(edge ed : adj[node][c]) {
                ll nw = d + sumw[node][c] - ed.w;
                if(nw < dp[ed.nxt]) {
                    dp[ed.nxt] = nw;
                    pq.push({dp[ed.nxt], {ed.nxt, 0}});
                }
            }

        } else {
            if(d != dp[node]) continue;
            for (auto x : adj[node]) {
                for(edge ed : x.ss) {
                    int nxt = ed.nxt;
                    int col = ed.col;
                    ll w = ed.w;

                    ll nw1 = d + w;
                    if(nw1 < dp[nxt]) {
                        dp[nxt] = nw1;
                        pq.push({dp[nxt], {nxt, 0}});
                    }

                    ll nw2 = d + sumw[node][col] - w;
                    if(nw2 < dp[nxt]) {
                        dp[nxt] = nw2;
                        pq.push({dp[nxt], {nxt, 0}});
                    }

                    ll nw3 = d;
                    if(dp2[nxt].count(col) == 0 || nw3 < dp2[nxt][col]) {
                        dp2[nxt][col] = nw3;
                        pq.push({dp2[nxt][col], {nxt, col}});
                    }


                }
            }
           
        }
    }
    cout << (dp[n - 1] == 1e18 ? -1 : dp[n-1]) << endl;
    
    //auto stop = chrono::high_resolution_clock::now();
    //auto duration = chrono::duration_cast<chrono::microseconds>(stop - start);
    //cout << duration.count() << endl;
    //cin.close();
    //cout.close();
}

Subtask #1
34.0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 6 ms 9684 KB Output is correct
5 Correct 5 ms 9720 KB Output is correct
6 Correct 6 ms 9684 KB Output is correct
7 Correct 6 ms 9904 KB Output is correct
8 Correct 5 ms 9684 KB Output is correct
9 Correct 9 ms 10404 KB Output is correct
10 Correct 8 ms 10252 KB Output is correct
11 Correct 6 ms 10068 KB Output is correct
12 Correct 7 ms 10068 KB Output is correct
13 Correct 7 ms 10180 KB Output is correct
14 Correct 7 ms 10068 KB Output is correct
15 Correct 6 ms 9940 KB Output is correct
16 Correct 9 ms 10116 KB Output is correct
17 Correct 7 ms 10120 KB Output is correct
18 Correct 6 ms 9952 KB Output is correct
19 Correct 7 ms 9940 KB Output is correct
20 Correct 6 ms 10068 KB Output is correct

Subtask #2
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 174 ms 30916 KB Output is correct
2 Correct 68 ms 20592 KB Output is correct
3 Correct 174 ms 27588 KB Output is correct
4 Correct 102 ms 24136 KB Output is correct
5 Correct 884 ms 83408 KB Output is correct
6 Correct 703 ms 72632 KB Output is correct
7 Correct 279 ms 53632 KB Output is correct
8 Correct 388 ms 50920 KB Output is correct
9 Correct 371 ms 50876 KB Output is correct
10 Correct 299 ms 45556 KB Output is correct
11 Correct 114 ms 31820 KB Output is correct

Subtask #3
42.0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 6 ms 9684 KB Output is correct
5 Correct 5 ms 9720 KB Output is correct
6 Correct 6 ms 9684 KB Output is correct
7 Correct 6 ms 9904 KB Output is correct
8 Correct 5 ms 9684 KB Output is correct
9 Correct 9 ms 10404 KB Output is correct
10 Correct 8 ms 10252 KB Output is correct
11 Correct 6 ms 10068 KB Output is correct
12 Correct 7 ms 10068 KB Output is correct
13 Correct 7 ms 10180 KB Output is correct
14 Correct 7 ms 10068 KB Output is correct
15 Correct 6 ms 9940 KB Output is correct
16 Correct 9 ms 10116 KB Output is correct
17 Correct 7 ms 10120 KB Output is correct
18 Correct 6 ms 9952 KB Output is correct
19 Correct 7 ms 9940 KB Output is correct
20 Correct 6 ms 10068 KB Output is correct
21 Correct 174 ms 30916 KB Output is correct
22 Correct 68 ms 20592 KB Output is correct
23 Correct 174 ms 27588 KB Output is correct
24 Correct 102 ms 24136 KB Output is correct
25 Correct 884 ms 83408 KB Output is correct
26 Correct 703 ms 72632 KB Output is correct
27 Correct 279 ms 53632 KB Output is correct
28 Correct 388 ms 50920 KB Output is correct
29 Correct 371 ms 50876 KB Output is correct
30 Correct 299 ms 45556 KB Output is correct
31 Correct 114 ms 31820 KB Output is correct
32 Correct 113 ms 23816 KB Output is correct
33 Correct 146 ms 25536 KB Output is correct
34 Correct 375 ms 47428 KB Output is correct
35 Correct 251 ms 38592 KB Output is correct
36 Correct 289 ms 46592 KB Output is correct
37 Correct 303 ms 49648 KB Output is correct
38 Correct 315 ms 57200 KB Output is correct
39 Correct 135 ms 27588 KB Output is correct
40 Correct 403 ms 52076 KB Output is correct
41 Correct 389 ms 52392 KB Output is correct
42 Correct 437 ms 60372 KB Output is correct
43 Correct 192 ms 33216 KB Output is correct
44 Correct 406 ms 38476 KB Output is correct
45 Correct 288 ms 47460 KB Output is correct
46 Correct 242 ms 47908 KB Output is correct
47 Correct 270 ms 49096 KB Output is correct
48 Correct 859 ms 85212 KB Output is correct