oj.uz

Submission #1036094

# Submission time Handle Problem Language Result Execution time Memory
1036094 2024-07-27T03:32:33 Z eueka Robot (JOI21_ho_t4) C++14
0 / 100
 318 ms 103740 KB 
#include <bits/stdc++.h>
#define ll long long
#define ii pair<ll, ll>
#define mo(i, a, b) for (int i = a; i <= b; i++)
#define me(i, a, b) for (int i = a; i >= b; i--)
#define bit(mask, i) ((mask >> i) & 1)
const ll N = 1e6 + 5;
const ll mod = 1e9 + 7;
const ll base = 31;
const ll inf = 1e18;
using namespace std;
struct linh{
    ll v, c, w;
}a[N];
linh canh[N];
ll d[N], n, m, ans = inf;
vector<linh> ke[N];
map<ll, ll> mp[N];
void dijk(ll s){
    mo(i, 1, n) d[i] = inf;
    priority_queue<ii, vector<ii>, greater<ii>> q;
    d[s] = 0;
    q.push({d[s], s});
    while(q.size()){
        ii top = q.top(); q.pop();
        ll kc = top.first, u = top.second;
        for(auto it: ke[u]){
            ll v = it.v, c = it.c, w = it.w;
            if(mp[u][c] == 1){
                if(d[v] > kc){
                    d[v] = kc;
                    q.push({d[v], v});
                }
            }
            else{
                if(d[v] > kc  + w){
                    d[v] = kc + w;
                    q.push({d[v], v});
                }
            }
        }
    }
}
int main()
{
    ///freopen("task.inp", "r", stdin);
    ///freopen("task.out", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    mo(i, 1, m){
        ll u, v, c, w; cin >> u >> v >> c >> w;
        ke[u].push_back({v, c, w});
        ke[v].push_back({u, c, w});
        mp[u][c]++;
        mp[v][c]++;
    }
    dijk(1);
    if(d[n] == inf) cout << -1;
    else cout << d[n];
    return 0;
}

Subtask #1
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 70740 KB Output is correct
2 Correct 29 ms 70748 KB Output is correct
3 Correct 35 ms 70900 KB Output is correct
4 Correct 30 ms 70792 KB Output is correct
5 Correct 29 ms 70736 KB Output is correct
6 Correct 30 ms 70740 KB Output is correct
7 Incorrect 38 ms 70996 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 82376 KB Output is correct
2 Correct 49 ms 76340 KB Output is correct
3 Correct 86 ms 86480 KB Output is correct
4 Correct 62 ms 78420 KB Output is correct
5 Incorrect 318 ms 103740 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 70740 KB Output is correct
2 Correct 29 ms 70748 KB Output is correct
3 Correct 35 ms 70900 KB Output is correct
4 Correct 30 ms 70792 KB Output is correct
5 Correct 29 ms 70736 KB Output is correct
6 Correct 30 ms 70740 KB Output is correct
7 Incorrect 38 ms 70996 KB Output isn't correct
8 Halted 0 ms 0 KB -