Submission #1036094

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036094		eueka	Robot (JOI21_ho_t4)	C++14	0 / 100	318 ms	103740 KiB

Main

#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
• Subtask 2: 0 / 24
• Subtask 3: 0 / 42