Submission #1293318

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293318		kiteyu	Robot (JOI21_ho_t4)	C++20	100 / 100	108 ms	23320 KiB

Main

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
using ll = long long;

const int N = 1e6;
const int M = 1e6;
const ll INF = 3e18;

int n,m;
struct edge{
    int u,v,c;
    ll d;
}a[M+5];

struct edg1{
    int v,c;
    ll d;
};
vector<edg1> g[N+5];
ll dist[N+5];
ll cost[M+5],mi[M+5];

void dji(int x){
    for(int i = 1 ; i <= n ; ++i) dist[i] = INF;
    priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>>pq;
    dist[x] = 0;
    pq.push({0,x});
    while(!pq.empty()){
        pair<ll,int> t = pq.top();
        pq.pop();
        ll w = t.fi;
        int u = t.se;
        if(dist[u] < w) continue;
        for(edg1 i : g[u]){
            mi[i.c] = INF;
            cost[i.c] = 0;
        }
        for(edg1 i : g[u]){
            mi[i.c] = min(mi[i.c],dist[i.v]);
            cost[i.c] += i.d;
        }

        for(edg1 i : g[u]){
            ll val = min(cost[i.c]-i.d,i.d);
            if(dist[i.v] > w + val){
                dist[i.v] = w + val;
                pq.push({dist[i.v],i.v});
            }
            if(dist[i.v] > mi[i.c] + cost[i.c] - i.d){
                dist[i.v] = mi[i.c] + cost[i.c] - i.d;
                pq.push({dist[i.v],i.v});
            }
        }
    }
    if(dist[n] >= INF) cout << -1 << '\n';
    else cout << dist[n];
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> m;
    for(int i = 1 ; i <= m ; ++i){
        cin >> a[i].u >> a[i].v >> a[i].c >> a[i].d;
        g[a[i].u].push_back({a[i].v,a[i].c,a[i].d});
        g[a[i].v].push_back({a[i].u,a[i].c,a[i].d});
    }

    dji(1);

    return 0;
}

• Subtask 1: 34 / 34
• Subtask 2: 24 / 24
• Subtask 3: 42 / 42