Submission #1315429

#	Time	Username	Problem	Language	Result	Execution time	Memory
1315429		vedchoudhary	Olympic Bus (JOI20_ho_t4)	C++20	5 / 100	1095 ms	5892 KiB

ho_t4

#include <bits/stdc++.h>
#pragma GCC optimize("O3")

using namespace std;

using ll = long long;
#define int ll

const int INF = (int)4e18;

struct Edge {
    int s,e;
    int c,d;
    Edge(){};
    Edge(int _u, int _v, int _c, int _d) : s(_u), e(_v), c(_c), d(_d) {};
};

bool operator < (const Edge& a, const Edge& b) {
    if(a.s!=b.s) return a.s < b.s;
    if(a.e!=b.e) return a.e < b.e;
    if(a.c!=b.c) return a.c < b.c;
    return a.d < b.d;
}

int n,m;
set<Edge> adj[201];
vector<Edge> e;

int dijkstra(int s, int e) {
    vector<int> dist(n+1,INF);
    vector<bool> seen(n+1,false);
    dist[s] = 0;
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq; pq.push({0,s});
    while(!pq.empty()) {
        auto [d,curr] = pq.top(); pq.pop();
        if(dist[curr]<d||seen[curr]) continue;
        for(Edge r : adj[curr]) {
            if(d+r.c<dist[r.e]&&!seen[r.e]) { pq.push({d+r.c,r.e}); dist[r.e] = d+r.c; }
        }
        seen[curr] = true;
    }
    return dist[e];
}

signed main() {
    cin >> n >> m;
    e.reserve(m);
    for(int i = 0; i < m; i++) {
        int u,v,c,d; cin >> u >> v >> c >> d;
        adj[u].insert(Edge(u,v,c,d));
        e.push_back(Edge(u,v,c,d));
    }
    int ans = dijkstra(1,n)+dijkstra(n,1);
    for(Edge r : e) {
        adj[r.s].erase(r);
        adj[r.e].insert(Edge(r.e,r.s,r.c,r.d));
        ans = min(ans,r.d+dijkstra(1,n)+dijkstra(n,1));
        adj[r.e].erase(Edge(r.e,r.s,r.c,r.d));
        adj[r.s].insert(r);
    }
    cout << ((ans<INF)?ans:-1);
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 11
• Subtask 3: 0 / 21
• Subtask 4: 0 / 63